pn2adg: handle dynamic control variables in generated AST
[ppn.git] / pn.cc
blob5a42d0fb0dc1dce7d69b44b32feff2dc6232bf63
1 #include <iostream>
2 #include <set>
3 #include <map>
4 #include <vector>
6 #include <isl/flow.h>
8 #include <isa/yaml.h>
9 #include <isa/pdg.h>
10 #include "da.h"
11 #include "size.h"
12 extern "C" {
13 #include "isl_util.h"
15 #include "translation.h"
16 #include "pn_options.h"
18 using pdg::PDG;
19 using namespace std;
20 using namespace da;
21 using namespace size;
23 /* Check whether node is a propagation node
25 * A propagation node simply copies a value from one array to another array.
26 * In principle, a copy node could also copy a value to the same array,
27 * but then we would have to be careful that the node does not recursively
28 * copy values.
29 * Note that the check is incomplete. If a node performs some additional
30 * operations involving only iterators, then this information is not stored
31 * so we may incorrectly conclude that the node is a copy node.
33 static bool propagation_node(pdg::node *node)
35 pdg::statement *s = node->statement;
36 if (s->accesses.size() != 2)
37 return false;
38 if (s->accesses[0]->type != pdg::access::read)
39 return false;
40 if (s->accesses[1]->type != pdg::access::write)
41 return false;
42 if (s->accesses[0]->array == s->accesses[1]->array)
43 return false;
44 if (s->accesses[1]->array->dims.size() != 0)
45 return false;
46 if (s->top_function && s->top_function->name &&
47 strcmp(s->top_function->name->s.c_str(), ""))
48 return false;
49 return true;
52 static pdg::IslMap *join_input(PDG *pdg, pdg::IslMap *left,
53 pdg::IslMap *right)
55 pdg::IslMap *res;
56 isl_ctx *ctx = pdg->get_isl_ctx();
57 isl_map *rel = left->get_isl_map(ctx);
58 isl_map *acc = right->get_isl_map(ctx);
60 acc = isl_map_apply_domain(acc, rel);
62 res = new pdg::IslMap(acc);
64 return res;
67 /* Given a dependence relation um_rel that maps iterations from
68 * a propagation node to the current node and an access relation
69 * from the current node, drop those iterations from the domain
70 * of the access relation that have been propagated, i.e.,
71 * that are in the range of the dependence relation.
73 * The original access relation is destroyed and a new one
74 * is returned, provided the new access relation is not empty.
75 * If it is empty, then a NULL pointer is returned.
77 * Note that the input access relation may not have been specialized
78 * to the domain of the node, i.e., the access relation may have
79 * a universe domain. In that case, the new relation is unlikely
80 * to be empty, but it may end up having a domain that is disjoint
81 * from the domain of the node.
83 static pdg::IslMap *remove_propagated_from_domain(PDG *pdg,
84 pdg::IslMap *um_rel, pdg::IslMap *um_acc)
86 pdg::IslMap *res = NULL;
87 isl_ctx *ctx = pdg->get_isl_ctx();
88 isl_map *rel = um_rel->get_isl_map(ctx);
89 isl_map *acc = um_acc->get_isl_map(ctx);
91 isl_set *rel_ran = isl_map_range(rel);
92 isl_set *acc_dom = isl_map_domain(isl_map_copy(acc));
94 acc_dom = isl_set_subtract(acc_dom, rel_ran);
95 acc = isl_map_intersect_domain(acc, acc_dom);
97 delete um_acc;
99 if (isl_map_is_empty(acc))
100 isl_map_free(acc);
101 else
102 res = new pdg::IslMap(acc);
104 return res;
107 /* Recursively replace old_access inside call by new_access.
109 static void replace_access(pdg::function_call *call, pdg::access *old_access,
110 pdg::call_or_access *new_coa)
112 for (int i = 0; i < call->arguments.size(); ++i) {
113 pdg::call_or_access *coa = call->arguments[i];
114 if (coa->type == pdg::call_or_access::t_call)
115 replace_access(coa->call, old_access, new_coa);
116 if (coa->type == pdg::call_or_access::t_access &&
117 coa->access == old_access) {
118 *coa = *new_coa;
119 break;
124 /* Replace old_access inside s by new_access.
125 * If empty is not set, then new_access only replaces part of
126 * old_access. This means that old_access is kept in the list
127 * of accesses and that in the parse tree of the statement,
128 * old_access is replaced by a new virtual function call
129 * with old_access and new_access as arguments.
131 static void replace_access(pdg::statement *s, pdg::access *old_access,
132 pdg::access *new_access, bool empty)
134 pdg::call_or_access coa;
136 if (empty)
137 s->accesses.erase(old_access);
138 s->accesses.push_back(new_access);
140 if (!s->top_function)
141 return;
143 if (empty) {
144 coa.type = pdg::call_or_access::t_access;
145 coa.access = new_access;
146 } else {
147 pdg::call_or_access *old_coa, *new_coa;
148 coa.type = pdg::call_or_access::t_call;
149 coa.call = new pdg::function_call;
150 coa.call->name = new str(string("#PHI"));
151 old_coa = new pdg::call_or_access;
152 old_coa->type = pdg::call_or_access::t_access;
153 old_coa->access = old_access;
154 coa.call->arguments.push_back(old_coa);
155 new_coa = new pdg::call_or_access;
156 new_coa->type = pdg::call_or_access::t_access;
157 new_coa->access = new_access;
158 coa.call->arguments.push_back(new_coa);
160 replace_access(s->top_function, old_access, &coa);
163 static void clear_dependences(PDG *pdg)
165 for (int j = 0; j < pdg->dependences.size(); ++j) {
166 pdg::dependence *dep = pdg->dependences[j];
167 delete dep->controlled_relation;
168 delete dep->relation;
169 delete dep;
171 pdg->dependences.resize(0);
174 /* Check if there is any node that simply copies the value from an array
175 * to a scalar. If so, perform dependence analysis on the scalar
176 * and replaces read access to the scalar that depend on writes from
177 * a propagation node to reads from the propagated array.
178 * In particular, the propagated iterations are removed from the access
179 * relation and replaced by an access to the propagated array.
180 * Finally, the propagation node is removed.
182 static void copy_propagation(PDG* pdg)
184 std::set<pdg::node *> to_remove_n;
185 for (int i = 0; i < pdg->nodes.size(); ++i) {
186 pdg::node *node = pdg->nodes[i];
187 pdg::statement *s = node->statement;
188 if (!propagation_node(node))
189 continue;
190 pdg::array *a = s->accesses[1]->array;
191 find_deps(pdg, a, flow);
192 std::set<pdg::access *> to_remove;
193 for (int j = 0; j < pdg->dependences.size(); ++j) {
194 pdg::dependence *dep = pdg->dependences[j];
195 if (dep->controlled_relation)
196 continue;
197 assert(dep->type == pdg::dependence::flow);
198 assert(dep->from != dep->to);
199 if (!propagation_node(dep->from))
200 continue;
201 to_remove_n.insert(dep->from);
202 pdg::IslMap *access_map = dep->from->statement->accesses[0]->map;
203 pdg::IslMap *prop_access = join_input(pdg, dep->relation, access_map);
204 access_map = dep->to_access->map;
205 access_map = remove_propagated_from_domain(pdg, dep->relation,
206 access_map);
207 dep->to_access->map = access_map;
208 bool empty = !access_map;
209 pdg::access *access = new pdg::access;
210 access->nr = dep->to_access->nr;
211 access->array = dep->from->statement->accesses[0]->array;
212 access->type = pdg::access::read;
213 access->map = prop_access;
214 replace_access(dep->to->statement, dep->to_access, access, empty);
215 if (empty)
216 to_remove.insert(dep->to_access);
218 std::set<pdg::access *>::iterator it;
219 for (it = to_remove.begin(); it != to_remove.end(); ++it) {
220 (*it)->array = NULL;
221 (*it)->free();
222 delete (*it);
224 clear_dependences(pdg);
226 if (to_remove_n.size() == 0)
227 return;
228 std::set<pdg::node *>::iterator itn;
229 for (itn = to_remove_n.begin(); itn != to_remove_n.end(); ++itn) {
230 (*itn)->statement->accesses[0]->array = NULL;
231 (*itn)->statement->accesses[1]->array = NULL;
232 (*itn)->free();
233 delete (*itn);
234 pdg->nodes.erase(*itn);
236 for (int i = 0; i < pdg->nodes.size(); ++i)
237 pdg->nodes[i]->nr = i;
240 /* Check whether dep writes and reads from consecutive iterations of
241 * the same domain.
242 * We check this property by testing whether any other read for the
243 * same access occurs in between.
245 bool is_consecutive_dep(PDG *pdg, pdg::dependence *dep, isl_map *map)
247 isl_ctx *ctx = pdg->get_isl_ctx();
248 assert(dep->to == dep->from);
249 for (int i = 0; i < pdg->dependences.size(); ++i) {
250 pdg::dependence *other_dep = pdg->dependences[i];
251 if (other_dep == dep)
252 continue;
253 if (other_dep->to != dep->to)
254 continue;
255 if (other_dep->to_access != dep->to_access)
256 continue;
257 isl_map *other_map = other_dep->relation->get_isl_map(ctx);
258 bool consec = isl_is_consecutive_dep(map, other_map);
259 isl_map_free(other_map);
260 if (!consec)
261 return false;
263 return true;
266 /* An auxiliary class that keeps a reference to an isl_map
267 * and frees it when it goes out of scope.
269 struct temp_map {
270 isl_map * const map;
271 temp_map(isl_map *m) : map(m) {}
272 operator isl_map *() const { return map; }
273 ~temp_map() {
274 isl_map_free(map);
278 /* Set *user to qp of the first call, assuming *user was initialized to NULL.
279 * If this function is called more than once, then return -1.
281 static int extract_single(__isl_take isl_set *set,
282 __isl_take isl_qpolynomial *qp, void *user)
284 isl_qpolynomial **res = (isl_qpolynomial **) user;
286 isl_set_free(set);
288 if (*res) {
289 isl_qpolynomial_free(qp);
290 return -1;
293 *res = qp;
294 return 0;
297 /* Check if we can use a shift register for the self-dependence dep
298 * on the domain D.
299 * If yes, return the required size of the shift register.
300 * If no, return NULL.
302 * We assume that the register is shifted on every iteration of D.
303 * If the number of shifts between any pair of writes and reads is
304 * constant, then we can use a shift register.
305 * Note that the size of the shift register may be larger than
306 * that of the FIFO, since there may be iterations of the domain
307 * between corresponding writes and reads where nothing is written
308 * to or read from the shift register.
310 * If "ref" is a wrapped map, then the iteration domain
311 * is in the domain of that map.
313 static size::enumerator *shift_register_size(pdg::PDG *pdg,
314 __isl_take isl_set *ref, __isl_take isl_map *dep)
316 isl_space *dims;
317 isl_set *dep_set;
318 isl_map *read_after_ref;
319 isl_map *write_before_ref;
320 isl_map *ref_between;
321 isl_pw_qpolynomial *pwqp;
322 isl_set *universe;
323 isl_qpolynomial *qp;
324 unsigned dim;
326 if (isl_set_is_wrapping(ref))
327 ref = isl_map_domain(isl_set_unwrap(ref));
329 dim = isl_set_dim(ref, isl_dim_set);
330 dep = isl_map_move_dims(dep, isl_dim_in, dim, isl_dim_out, 0, dim);
331 dep_set = isl_map_domain(dep);
333 read_after_ref = isl_map_lex_ge(isl_set_get_space(ref));
334 read_after_ref = isl_map_insert_dims(read_after_ref, isl_dim_in, 0, dim);
335 write_before_ref = isl_map_lex_lt(isl_set_get_space(ref));
336 write_before_ref = isl_map_add_dims(write_before_ref, isl_dim_in, dim);
337 ref_between = isl_map_intersect(read_after_ref, write_before_ref);
339 ref_between = isl_map_intersect_range(ref_between, ref);
340 ref_between = isl_map_intersect_domain(ref_between,
341 isl_set_copy(dep_set));
343 pwqp = isl_map_card(ref_between);
345 pwqp = isl_pw_qpolynomial_gist(pwqp, dep_set);
347 pwqp = isl_pw_qpolynomial_coalesce(pwqp);
349 qp = NULL;
350 if (isl_pw_qpolynomial_foreach_piece(pwqp, &extract_single, &qp) < 0 ||
351 !qp ||
352 isl_qpolynomial_involves_dims(qp, isl_dim_in, 0, dim + dim)) {
353 isl_qpolynomial_free(qp);
354 isl_pw_qpolynomial_free(pwqp);
355 return NULL;
357 isl_pw_qpolynomial_free(pwqp);
359 qp = isl_qpolynomial_project_domain_on_params(qp);
360 universe = isl_set_universe(isl_qpolynomial_get_domain_space(qp));
361 pwqp = isl_pw_qpolynomial_alloc(universe, qp);
363 return new size::enumerator(pwqp, pdg);
366 /* isl_access_level_before function used in a context where there
367 * is a single iteration domain. The order is given by the order
368 * of the accesses passed through first and second.
369 * If the first access precedes the second, we return 2 * d + 1,
370 * where d is the dimension of the iteration domain, and otherwise 2 * d.
372 static int precedes_access(void *first, void *second)
374 pdg::access *access1 = (pdg::access *) first;
375 pdg::access *access2 = (pdg::access *) second;
376 int d = isl_map_dim(access1->map->map, isl_dim_in);
378 return 2 * d + (access1->nr < access2->nr);
381 /* Return true if all input dimensions are constrained to be equal to the
382 * corresponding output dimensions.
384 static bool is_identity_map(__isl_keep isl_map *map)
386 int is_id;
387 isl_space *space = isl_map_get_space(map);
388 isl_map *id = isl_map_identity(space);
390 is_id = isl_map_is_subset(map, id);
392 isl_map_free(id);
394 return is_id;
397 /* Set buf (of size buf_len) to the prefix of control variables
398 * that correspond to the from and to access of the given "dep"
399 * and return the length of the prefix.
401 static size_t set_local_control_name(char *buf, size_t buf_len,
402 pdg::dependence *dep)
404 snprintf(buf, buf_len, "__last_%s_%d_%s_%d",
405 dep->from->name->s.c_str(), dep->from_access->nr,
406 dep->to->name->s.c_str(), dep->to_access->nr);
407 return strlen(buf);
410 /* Given the name of a binding variable, reset the part that refers
411 * to the sink access by "nr".
413 * The original name is of the form
415 * __last_ND_<source node>_<source access>_ND_<sink node>_<sink access>_*
417 * We simply replace the <sink access> by <nr>.
419 static str *replace_to_access(isl_ctx *ctx, str *id, int nr)
421 const char *name;
422 const char *suffix;
423 const char *infix;
424 char *replaced;
425 size_t len;
426 str *s;
428 name = id->s.c_str();
429 assert(name);
430 suffix = strrchr(name, '_');
431 assert(suffix);
432 infix = (const char *) memrchr(name, '_', suffix - name);
433 assert(infix);
434 len = infix + 1 - name + strlen(suffix) + 20;
435 replaced = isl_alloc_array(ctx, char, len);
436 assert(replaced);
437 len = infix + 1 - name;
438 memcpy(replaced, name, len);
439 snprintf(replaced + len, 20, "%d", nr);
440 len += strlen(replaced + len);
441 strcpy(replaced + len, suffix);
443 s = new str(replaced);
444 free(replaced);
446 return s;
449 /* For each element of controls, replace the part of the name that
450 * refers to the sink access by "nr" and collect the results in
451 * renamed_controls.
453 static void replace_to_access(isl_ctx *ctx, seq<str> &renamed_controls,
454 seq<str> &controls, int nr)
456 for (int i = 0; i < controls.size(); ++i)
457 renamed_controls.push_back(replace_to_access(ctx,
458 controls[i], nr));
461 /* Is the i-th parameter of "map" of the form __last_*
462 * but not of the form local_control*?
464 static bool is_foreign_control(__isl_keep isl_map *map, int i,
465 const char *local_control, size_t len)
467 const char *name;
468 const char *prefix = "__last_";
469 size_t prefix_len = strlen(prefix);
471 if (!isl_map_has_dim_id(map, isl_dim_param, i))
472 return false;
473 name = isl_map_get_dim_name(map, isl_dim_param, i);
474 if (strncmp(name, prefix, prefix_len))
475 return false;
476 return strncmp(name, local_control, len) != 0;
479 /* Remove from "dep" all those parameters that are of the form __last_*
480 * but not of the form local_control* and return the result.
482 static __isl_give isl_map *remove_foreign_controls(__isl_take isl_map *dep,
483 const char *local_control, size_t len)
485 int n_param;
487 n_param = isl_map_dim(dep, isl_dim_param);
488 for (int i = n_param - 1; i >= 0; --i) {
489 if (!is_foreign_control(dep, i, local_control, len))
490 continue;
491 dep = isl_map_project_out(dep, isl_dim_param, i, 1);
493 dep = isl_map_coalesce(dep);
495 return dep;
498 /* Is the i-th parameter of "map" a control, i.e., a parameter
499 * introduced by convert_writer()?
500 * In particular, is the parameter of the form __last_*?
502 static bool is_control(__isl_keep isl_map *map, int i)
504 const char *name;
505 const char *prefix = "__last_";
506 size_t prefix_len = strlen(prefix);
508 if (!isl_map_has_dim_id(map, isl_dim_param, i))
509 return false;
510 name = isl_map_get_dim_name(map, isl_dim_param, i);
511 return strncmp(name, prefix, prefix_len) == 0;
514 /* Remove all parameters that were introduced by convert_writer().
516 static __isl_give isl_map *remove_all_controls(__isl_take isl_map *dep)
518 int n_param;
520 n_param = isl_map_dim(dep, isl_dim_param);
521 for (int i = n_param - 1; i >= 0; --i) {
522 if (!is_control(dep, i))
523 continue;
524 dep = isl_map_project_out(dep, isl_dim_param, i, 1);
526 dep = isl_map_coalesce(dep);
528 return dep;
531 struct add_reuse_data {
532 PDG *pdg;
533 pdg::dependence *dep;
536 extern "C" {
537 static int add_reuse(__isl_take isl_map *dep_rel, int must,
538 void *dep_user, void *user);
541 /* Add a reuse dependence with dependence relation "dep_rel" to
542 * data->pdg->dependences.
543 * data->dep corresponds to the original dependence that is reusing
544 * some value that was previously used by "propagate_access", from
545 * the same node.
546 * Since "dep_rel" was obtained from a relation with local
547 * control variables, we need to remove them to obtain the
548 * dependence relation on the reuse dependence.
550 * If we are reusing control variables, then we need to rename
551 * the from_control to refer to the access where we are reusing
552 * the control variables from.
554 * If the dependence relations maps iterations to themselves, then
555 * we mark the new reuse dependence as a wire.
557 static int add_reuse(__isl_take isl_map *dep_rel, int must, void *dep_user,
558 void *user)
560 pdg::access *propagate_access = (pdg::access *) dep_user;
561 add_reuse_data *data = (add_reuse_data *) user;
562 pdg::dependence *reuse_dep;
563 isl_ctx *ctx = isl_map_get_ctx(dep_rel);
565 reuse_dep = new pdg::dependence;
566 reuse_dep->array = data->dep->array;
567 replace_to_access(ctx, reuse_dep->from_controls,
568 data->dep->from_controls, propagate_access->nr);
569 reuse_dep->to_controls = data->dep->to_controls;
570 reuse_dep->from = data->dep->to;
571 reuse_dep->to = data->dep->to;
572 reuse_dep->from_access = propagate_access;
573 reuse_dep->to_access = data->dep->to_access;
574 if (reuse_dep->from == reuse_dep->to && is_identity_map(dep_rel))
575 reuse_dep->type = pdg::dependence::pn_wire;
576 else
577 reuse_dep->type = data->dep->type;
578 if (data->dep->controlled_relation) {
579 pdg::IslMap *cr = data->dep->controlled_relation;
580 isl_set *dom = isl_map_range(cr->get_isl_map());
581 isl_map *control_rel = isl_map_copy(dep_rel);
582 control_rel = isl_map_intersect_range(control_rel, dom);
583 reuse_dep->controlled_relation = new pdg::IslMap(control_rel);
585 dep_rel = remove_all_controls(dep_rel);
586 reuse_dep->relation = new pdg::IslMap(dep_rel);
587 data->pdg->dependences.push_back(reuse_dep);
589 return 0;
592 /* Detect reuse among the dependences in "deps", adding split off
593 * dependences to pdg->dependences.
594 * Each of the dependences in "deps" originates from the same
595 * write access and ends in the same node.
597 * We look for values, i.e., iterations of the write access,
598 * that are used several times. To do so, we perform dependence
599 * analysis on the inverted dependence relations. That is,
600 * we use these inverted dependence relations as "access relations",
601 * accessing iterations of the write access.
602 * We consider each dependence in turn as a "read", each time taking
603 * all dependences as writes.
604 * In the result of such a dependence analysis, the "uninitialized reads"
605 * correspond to the first use of a result from the original write access,
606 * while all the "dependences" corespond to a propagation of a value
607 * from one original read access to another original read access.
609 * If the dependence has a controlled_relation, then we use this
610 * controlled_relation as the "access relation" after removing all
611 * the foreign controls. This ensures that we only reuse data if
612 * the last iteration hasn't changed.
613 * After restricting the range of the controlled_relation based on
614 * the "uninitialized reads", we recompute the uncontrolled relation
615 * from this result.
617 * If there is only one dependence in "deps" and if that dependence
618 * is single-valued, then obviously there can be no reuse, so we skip
619 * the analysis.
621 * We currently assume that none of the accesses has an extended_relation.
623 static void detect_reuse(PDG *pdg, std::vector<pdg::dependence *> &deps)
625 add_reuse_data data = { pdg };
626 char buf[120];
627 size_t len;
629 if (deps.size() == 1 &&
630 isl_map_is_single_valued(deps[0]->relation->map))
631 return;
633 for (int i = 0; i < deps.size(); ++i) {
634 isl_access_info *ai;
635 isl_flow *flow;
636 isl_set *first;
637 isl_map *local;
638 pdg::IslMap *rel;
640 assert(!deps[i]->extended_relation);
642 if (deps[i]->controlled_relation) {
643 local = deps[i]->controlled_relation->get_isl_map();
644 len = set_local_control_name(buf, sizeof(buf), deps[i]);
645 local = remove_foreign_controls(local, buf, len);
646 } else
647 local = deps[i]->relation->get_isl_map();
648 local = isl_map_reverse(local);
650 data.dep = deps[i];
651 ai = isl_access_info_alloc(isl_map_copy(local),
652 deps[i]->to_access, &precedes_access, deps.size());
653 for (int j = 0; j < deps.size(); ++j) {
654 isl_map *map;
655 if (i == j) {
656 map = isl_map_copy(local);
657 } else {
658 map = deps[j]->relation->get_isl_map();
659 map = isl_map_reverse(map);
661 ai = isl_access_info_add_source(ai, map,
662 1, deps[j]->to_access);
664 flow = isl_access_info_compute_flow(ai);
665 isl_flow_foreach(flow, &add_reuse, &data);
666 first = isl_map_domain(isl_flow_get_no_source(flow, 1));
667 isl_flow_free(flow);
669 rel = deps[i]->relation;
670 if (deps[i]->controlled_relation) {
671 pdg::IslMap *cr = deps[i]->controlled_relation;
672 cr->map = isl_map_intersect_range(cr->map, first);
673 isl_map_free(rel->map);
674 rel->map = remove_all_controls(isl_map_copy(cr->map));
675 } else
676 rel->map = isl_map_intersect_range(rel->map, first);
678 isl_map_free(local);
682 /* Has this dependence been created during the detection
683 * of multiple assignments? In particular, does this dependence
684 * propagate the values in the source.
686 static bool is_multi_assignment_propagation(pdg::dependence *dep)
688 return dep->to_access == dep->from_access &&
689 dep->to_access->type == pdg::access::write;
692 typedef std::pair<pdg::access *, pdg::node *> an_pair;
693 typedef std::pair<int, an_pair> nan_triple;
695 struct nan_triple_cmp {
696 bool operator()(nan_triple t1, nan_triple t2) const {
697 if (t1.first != t2.first)
698 return t1.first < t2.first;
699 if (t1.second.first->nr != t2.second.first->nr)
700 return t1.second.first->nr < t2.second.first->nr;
701 return t1.second.second->nr < t2.second.second->nr;
705 typedef std::map<nan_triple, std::vector<pdg::dependence *>, nan_triple_cmp>
706 nan2deps;
708 /* Detect reuse of the same value (originating from the same
709 * write access) within a node and split the corresponding dependence
710 * into part of the original dependences that use the value for
711 * the first time and internal dependences that propagate the value.
713 * If a scheduling is applied that changes the order of the iterations
714 * within a given node, then this scheduling should be performed
715 * before the reuse detection.
717 * We first collect the dependences that originate in a given access
718 * and end up in a given node and then process each such collection
719 * in turn, in an order that does not depend on pointer values.
720 * While collecting dependences, we skip those that correspond
721 * to the propagation of multiple assignments to the next potential
722 * assignment.
724 * Dependences that propagate data (those that have a dep->array)
725 * are treated separately from those that propagate control.
727 * If the user has turned off reuse detection, then we do nothing.
729 static void detect_reuse(PDG *pdg, struct pn_options *options)
731 nan2deps access_deps;
732 nan2deps control_deps;
733 nan2deps::iterator it;
735 if (!options->reuse)
736 return;
738 for (int i = 0; i < pdg->dependences.size(); ++i) {
739 pdg::dependence *dep = pdg->dependences[i];
740 if (dep->type == pdg::dependence::uninitialized)
741 continue;
742 if (is_multi_assignment_propagation(dep))
743 continue;
744 an_pair p(dep->from_access, dep->to);
745 nan_triple t(dep->from->nr, p);
746 if (dep->array)
747 access_deps[t].push_back(dep);
748 else
749 control_deps[t].push_back(dep);
752 for (it = access_deps.begin(); it != access_deps.end(); ++it)
753 detect_reuse(pdg, it->second);
754 for (it = control_deps.begin(); it != control_deps.end(); ++it)
755 detect_reuse(pdg, it->second);
758 /* isl_access_level_before function used in a context where the
759 * iteration domains live in a common space. We therefore just
760 * need to retun 2 * the dimension of this space, which is stored
761 * in *first (and *second).
763 static int common_space(void *first, void *second)
765 int depth = *(int *) first;
766 return 2 * depth;
769 /* Assign dep to *user. This function is expected to be called
770 * exactly once.
772 static int extract_dep(__isl_take isl_map *dep, int must,
773 void *dep_user, void *user)
775 isl_map **map_p = (isl_map **) user;
777 *map_p = dep;
779 return 0;
782 /* Is the i-th parameter of "set" of the form __last_*
783 * but not of the form local_control*?
785 static bool is_foreign_control(__isl_keep isl_set *set, int i,
786 const char *local_control, size_t len)
788 const char *name;
789 const char *prefix = "__last_";
790 size_t prefix_len = strlen(prefix);
792 if (!isl_set_has_dim_id(set, isl_dim_param, i))
793 return false;
794 name = isl_set_get_dim_name(set, isl_dim_param, i);
795 if (strncmp(name, prefix, prefix_len))
796 return false;
797 return strncmp(name, local_control, len) != 0;
800 /* Does "set" have any parameters of the form __last_*
801 * that are not of the form local_control*?
803 static __isl_give isl_set *remove_foreign_controls(__isl_take isl_set *set,
804 const char *local_control, size_t len)
806 int n_param;
808 n_param = isl_set_dim(set, isl_dim_param);
809 for (int i = n_param - 1; i >= 0; --i) {
810 if (!is_foreign_control(set, i, local_control, len))
811 continue;
812 set = isl_set_project_out(set, isl_dim_param, i, 1);
814 set = isl_set_coalesce(set);
816 return set;
819 /* Given a dependence such that the dependence relation
820 * is not injective, split the dependence into two parts,
821 * one that propagates the value from a potential source iteration
822 * to the next potential source iteration and one that sends
823 * the data from the final potential source iteration to the sink
824 * iteration.
826 * The dependence may either be a control dependence, propagating
827 * control variables, or a data dependence, in which case it has
828 * a controlled_relation and it is the uncontrolled relation that
829 * is not injective.
831 * To obtain the last potential source iteration, we simply
832 * compute the lexicographic maximum of all potential source iterations.
834 * To obtain the dependence from one potential source iteration
835 * to the next potential source iteration, we apply
836 * dependence analysis on the dependence relation.
837 * In particular, we need a mapping from source iterations to
838 * the next source iteration associated to the same sink iteration,
839 * so we simply treat the original dependence relation as an access relation.
841 * The mapping to the next potential source should not have any controls.
842 * If the input dependence is a control dependence, then it is propagating
843 * control variables itself. If it is a data dependence, then we want
844 * to propagate values to the next potential source independently of
845 * any control.
847 * The constraints on the controls for the dependence from the final
848 * potential source iteration should be the same as those on the
849 * original relation, when seen from the destination node.
851 * We currently assume that there is no extended relation associated
852 * to the dependence.
854 static void split_multi_assignment(PDG *pdg, pdg::dependence *dep)
856 isl_set *dom;
857 isl_map *last;
858 isl_map *next = NULL;
859 isl_access_info *ai;
860 isl_flow *flow;
861 int depth;
862 pdg::dependence *next_dep;
863 char buf[120];
864 size_t len;
866 assert(!dep->extended_relation);
868 len = set_local_control_name(buf, sizeof(buf), dep);
870 depth = isl_map_dim(dep->relation->map, isl_dim_in);
871 ai = isl_access_info_alloc(isl_map_copy(dep->relation->map),
872 &depth, &common_space, 1);
873 ai = isl_access_info_add_source(ai, isl_map_copy(dep->relation->map),
874 1, &depth);
875 flow = isl_access_info_compute_flow(ai);
876 isl_flow_foreach(flow, &extract_dep, &next);
877 isl_flow_free(flow);
879 last = isl_map_copy(dep->relation->map);
880 last = isl_map_reverse(isl_map_lexmax(isl_map_reverse(last)));
882 next_dep = new pdg::dependence;
883 next_dep->array = dep->array;
884 next_dep->from_controls = dep->from_controls;
885 next_dep->to_controls = dep->to_controls;
886 next_dep->type = dep->type;
887 next_dep->from = dep->from;
888 next_dep->to = dep->from;
889 next_dep->from_access = dep->from_access;
890 next_dep->to_access = dep->from_access;
891 next_dep->relation = new pdg::IslMap(next);
892 pdg->dependences.push_back(next_dep);
894 dep->relation->map = isl_map_intersect(dep->relation->map, last);
895 if (dep->controlled_relation)
896 dep->controlled_relation->map =
897 isl_map_intersect_range(isl_map_copy(dep->relation->map),
898 isl_map_range(dep->controlled_relation->map));
901 /* If any sink iteration has more than one potential source
902 * iteration, we split off the propagation of the data on the from
903 * node from the transfer of the data to the to node.
905 * We only perform this operation here on (data) dependences
906 * with a "controlled_relation". The corresponding control dependence
907 * has already been handled from within extract_control_dependence.
908 * Other data dependences have an exact dependence relation and
909 * can therefore not exhibit multiple assignments.
911 static void split_multi_assignment(PDG *pdg)
913 for (int i = 0; i < pdg->dependences.size(); ++i) {
914 pdg::dependence *dep = pdg->dependences[i];
915 if (!dep->controlled_relation)
916 continue;
917 if (isl_map_is_injective(dep->relation->map))
918 continue;
919 split_multi_assignment(pdg, dep);
923 /* Does "dep" have any parameters of the form __last_*?
925 static bool has_controls(__isl_keep isl_map *dep)
927 int n_param;
928 const char *prefix = "__last_";
929 size_t prefix_len = strlen(prefix);
931 n_param = isl_map_dim(dep, isl_dim_param);
932 for (int i = 0; i < n_param; ++i) {
933 const char *name;
935 if (!isl_map_has_dim_id(dep, isl_dim_param, i))
936 continue;
937 name = isl_map_get_dim_name(dep, isl_dim_param, i);
938 if (!strncmp(name, prefix, prefix_len))
939 return true;
942 return false;
945 /* Is the i-th parameter of "map" of the form local_control*?
946 * "len" is the length of "local_control".
948 static bool is_local_control(__isl_keep isl_map *map, int i,
949 const char *local_control, size_t len)
951 const char *name;
953 if (!isl_map_has_dim_id(map, isl_dim_param, i))
954 return false;
955 name = isl_map_get_dim_name(map, isl_dim_param, i);
956 return strncmp(name, local_control, len) == 0;
959 /* Does "dep" have any parameters of the form __last_*
960 * that are not of the form local_control*?
962 static bool has_foreign_controls(__isl_keep isl_map *dep,
963 const char *local_control, size_t len)
965 int n_param;
967 n_param = isl_map_dim(dep, isl_dim_param);
968 for (int i = 0; i < n_param; ++i)
969 if (is_foreign_control(dep, i, local_control, len))
970 return true;
972 return false;
975 /* Does "dep" have any parameters of the form local_control*?
976 * "len" is the length of "local_control".
978 static bool has_local_controls(__isl_keep isl_map *dep,
979 const char *local_control, size_t len)
981 int n_param;
983 n_param = isl_map_dim(dep, isl_dim_param);
984 for (int i = 0; i < n_param; ++i)
985 if (is_local_control(dep, i, local_control, len))
986 return true;
988 return false;
991 /* Extract a control dependence from a dependence with a controlled_relation.
992 * The control dependence transfers the values of the control variables
993 * that correspond to the given dependence, i.e., those that correspond
994 * to the from and to access of the dependence.
995 * We therefore don't need to do anything if the controlled_relation
996 * only involves foreign controls.
998 * from_controls and to_controls are set from the local control variables
999 * in dep->controlled_relation.
1001 * The uncontrolled dependence relation may not be injective,
1002 * in which case the initial dependence relation on the control
1003 * dependence is also non-injective. In such cases, the control
1004 * dependence is split using split_multi_assignment in two parts,
1005 * one that propagate the current value of the controls to the next
1006 * iteration of the source and one that sends the final values to the sink.
1007 * The data dependence is split later on.
1009 static void extract_control_dependence(PDG *pdg, pdg::dependence *dep)
1011 pdg::dependence *control;
1012 char buf[120];
1013 size_t len;
1014 int n_param;
1015 isl_map *rel;
1017 len = set_local_control_name(buf, sizeof(buf), dep);
1018 rel = dep->controlled_relation->map;
1019 if (!has_local_controls(rel, buf, len))
1020 return;
1021 n_param = isl_map_dim(rel, isl_dim_param);
1023 control = new pdg::dependence;
1024 control->type = dep->type;
1025 control->from = dep->from;
1026 control->to = dep->to;
1027 control->from_access = dep->from_access;
1028 control->to_access = dep->to_access;
1029 control->relation = new pdg::IslMap(dep->relation->get_isl_map());
1030 for (int i = 0; i < n_param; ++i) {
1031 const char *name;
1032 if (!isl_map_has_dim_id(rel, isl_dim_param, i))
1033 continue;
1034 name = isl_map_get_dim_name(rel, isl_dim_param, i);
1035 if (strncmp(name, buf, len) != 0)
1036 continue;
1037 control->from_controls.push_back(new str(name));
1038 control->to_controls.push_back(new str(name));
1040 pdg->dependences.push_back(control);
1042 if (isl_map_is_injective(control->relation->map))
1043 return;
1044 split_multi_assignment(pdg, control);
1047 /* Extract a control dependence from each dependence with a controlled_relation.
1049 static void extract_control_dependences(PDG *pdg)
1051 int n_dep = pdg->dependences.size();
1053 for (int i = 0; i < n_dep; ++i) {
1054 pdg::dependence *dep = pdg->dependences[i];
1055 if (!dep->controlled_relation)
1056 continue;
1057 extract_control_dependence(pdg, dep);
1061 /* Split off the communication of data, along with the corresponding
1062 * controls, from selecting the data based on other controls.
1063 * "dep" is modified to only refer to the controls that correspond
1064 * to the given from and to access and an extra wire is introduced
1065 * to select the data.
1066 * If "dep" corresponds to a propagation from one potential source
1067 * to the next potential source, then it already only refers to
1068 * "local" controls. We handle this case separately so that we
1069 * don't have to add a special case to set_local_control_name
1070 * for setting up the right name for local controls on such dependences.
1072 * A new virtual access is created to act as the target of the modified
1073 * communication dependence and the source of the selection dependence.
1074 * If the input "dep" did not refer to the corresponding controls,
1075 * then the output "dep" does not refer to any control and
1076 * controlled_relation is cleared.
1078 static void split_wire(PDG *pdg, pdg::dependence *dep)
1080 isl_space *space;
1081 isl_set *dom;
1082 isl_map *rel;
1083 isl_map *id;
1084 pdg::dependence *wire;
1085 pdg::access *access;
1086 char buf[120];
1087 size_t len;
1089 if (is_multi_assignment_propagation(dep))
1090 return;
1092 assert(!dep->extended_relation);
1094 rel = dep->controlled_relation->map;
1095 len = set_local_control_name(buf, sizeof(buf), dep);
1097 if (!has_foreign_controls(rel, buf, len))
1098 return;
1100 space = isl_map_get_space(dep->controlled_relation->map);
1101 space = isl_space_range(space);
1102 space = isl_space_map_from_set(space);
1103 id = isl_map_identity(space);
1104 dom = isl_map_range(isl_map_copy(dep->controlled_relation->map));
1105 id = isl_map_intersect_domain(id, dom);
1107 access = new pdg::access;
1108 access->array = dep->to_access->array;
1109 access->nr = dep->to->statement->accesses.size();
1110 dep->to->statement->accesses.push_back(access);
1112 wire = new pdg::dependence;
1113 wire->array = dep->array;
1114 wire->type = pdg::dependence::pn_wire;
1115 wire->from = dep->to;
1116 wire->to = dep->to;
1117 wire->from_access = access;
1118 wire->to_access = dep->to_access;
1119 wire->relation = new pdg::IslMap(id);
1120 pdg->dependences.push_back(wire);
1122 dep->to_access = access;
1123 dep->controlled_relation->map = remove_foreign_controls(rel, buf, len);
1124 if (!has_controls(dep->controlled_relation->map)) {
1125 delete dep->controlled_relation;
1126 dep->controlled_relation = NULL;
1130 /* If the dependence involves "foreign" controls, i.e., controls
1131 * that correspond to other dependences, then we split off
1132 * the communication of the data (along with the "local" controls)
1133 * from the selection of the data based on the foreign controls.
1135 static void split_wires(PDG *pdg)
1137 for (int i = 0; i < pdg->dependences.size(); ++i) {
1138 pdg::dependence *dep = pdg->dependences[i];
1139 if (!dep->controlled_relation)
1140 continue;
1141 split_wire(pdg, dep);
1145 static void schedule(PDG *pdg, struct pn_options *options)
1147 translate(pdg, options->move);
1150 /* Compute the size of the dependence "dep" with scheduled dependence
1151 * relation "dep_map".
1153 * If "dep" is of type pn_union, then it may contains parts that read
1154 * from the channel in the same iteration. We therefore need to recombine
1155 * the dependence relations of those parts, but separate them apart.
1156 * In particular, we add an extra inner dimension with a fixed value
1157 * corresponding to the index of the dependence.
1159 static size::enumerator *compute_size(pdg::PDG *pdg, pdg::dependence *dep,
1160 __isl_take isl_map *dep_map, pn_options *options)
1162 dep_map = isl_map_copy(dep_map);
1163 if (dep->type == pdg::dependence::pn_union) {
1164 isl_space *space = isl_map_get_space(dep_map);
1165 int n_in, n_out;
1167 n_in = isl_space_dim(space, isl_dim_in);
1168 n_out = isl_space_dim(space, isl_dim_out);
1169 space = isl_space_add_dims(space, isl_dim_in, 1);
1170 space = isl_space_add_dims(space, isl_dim_out, 1);
1171 isl_map_free(dep_map);
1172 dep_map = isl_map_empty(space);
1173 for (int i = 0; i < pdg->dependences.size(); ++i) {
1174 pdg::dependence *part = pdg->dependences[i];
1175 isl_map *map_i;
1177 if (part->type != pdg::dependence::pn_part)
1178 continue;
1179 if (part->container != dep)
1180 continue;
1181 map_i = part->relation->get_isl_map();
1182 map_i = isl_map_intersect_params(map_i,
1183 pdg->get_context_isl_set());
1184 map_i = schedule_dependence(pdg, dep, map_i);
1185 map_i = isl_map_add_dims(map_i, isl_dim_in, 1);
1186 map_i = isl_map_add_dims(map_i, isl_dim_out, 1);
1187 map_i = isl_map_fix_si(map_i, isl_dim_in, n_in, i);
1188 map_i = isl_map_fix_si(map_i, isl_dim_out, n_out, i);
1189 dep_map = isl_map_union(dep_map, map_i);
1192 return selfloop_size(pdg, dep_map, options->size);
1195 static bool determine_dependence_properties(PDG *pdg, pdg::dependence *dep,
1196 bool evaluate, bool scheduled, struct pn_options *options)
1198 if (dep->type == pdg::dependence::uninitialized) {
1199 fprintf(stderr,
1200 "access to uninitialized data from %s on line %d\n",
1201 dep->array->name->s.c_str(), dep->to->statement->line);
1202 dep->relation->Dump(stderr);
1203 return scheduled;
1205 pdg::IslMap *rel = dep->relation;
1206 if (dep->type == pdg::dependence::pn_part ||
1207 dep->type == pdg::dependence::pn_wire) {
1208 dep->reordering = 0;
1209 dep->multiplicity = 0;
1210 dep->size = new pdg::enumerator(0);
1211 dep->value_size = new integer(0);
1212 return scheduled;
1215 isl_map *dep_map = rel->get_isl_map();
1216 dep_map = isl_map_intersect_params(dep_map, pdg->get_context_isl_set());
1217 dep->reordering = isl_map_is_reordering(dep_map);
1218 dep->multiplicity = 0;
1219 if (!options->reuse)
1220 dep->multiplicity = isl_map_has_multiplicity(dep_map);
1221 if (dep->reordering || dep->multiplicity) {
1222 isl_map_free(dep_map);
1223 return scheduled;
1226 if (dep->to != dep->from && !scheduled) {
1227 schedule(pdg, options);
1228 scheduled = true;
1231 if (dep->to != dep->from)
1232 dep_map = schedule_dependence(pdg, dep, dep_map);
1234 if (!dep->controlled_relation && isl_is_consecutive_loop(dep_map)) {
1235 dep->size = new pdg::enumerator(1);
1236 dep->value_size = new integer(1);
1237 if (dep->from_access == dep->to_access &&
1238 dep->to_access->type != pdg::access::write &&
1239 is_consecutive_dep(pdg, dep, dep_map))
1240 dep->type = pdg::dependence::pn_hold;
1241 } else {
1242 size::enumerator *size = NULL;
1243 if (options->shift_register && dep->to == dep->from &&
1244 !dep->controlled_relation) {
1245 isl_set *ref = dep->to->source->get_isl_set();
1246 size = shift_register_size(pdg, ref,
1247 isl_map_copy(dep_map));
1249 if (size)
1250 dep->type = pdg::dependence::pn_shift;
1251 else
1252 size = compute_size(pdg, dep, dep_map, options);
1253 if (size) {
1254 dep->size = *size;
1255 if (evaluate)
1256 dep->value_size = size->evaluate();
1257 delete size;
1261 isl_map_free(dep_map);
1263 return scheduled;
1266 static void determine_dependence_properties(PDG *pdg, bool evaluate,
1267 bool scheduled, struct pn_options *options)
1269 for (int i = 0; i < pdg->dependences.size(); ++i) {
1270 pdg::dependence *dep = pdg->dependences[i];
1271 scheduled = determine_dependence_properties(pdg, dep, evaluate,
1272 scheduled, options);
1276 /* Can we merge "dep1" and "dep2"?
1278 * That is,
1279 * - do they connect the same from_access to the same to node?
1280 * - is there no reordering in the combined dependence relation?
1282 static bool can_merge(PDG *pdg, pdg::dependence *dep1, pdg::dependence *dep2)
1284 pdg::IslMap *rel1 = dep1->relation;
1285 pdg::IslMap *rel2 = dep2->relation;
1286 isl_map *dep_rel;
1287 bool reordering;
1289 if (dep1->to != dep2->to)
1290 return false;
1291 if (dep1->from_access != dep2->from_access)
1292 return false;
1293 dep_rel = isl_map_union(rel1->get_isl_map(), rel2->get_isl_map());
1294 dep_rel = isl_map_intersect_params(dep_rel, pdg->get_context_isl_set());
1296 reordering = isl_map_is_reordering(dep_rel);
1298 isl_map_free(dep_rel);
1300 return !reordering;
1303 /* Combine the dependences "dep1" and "dep2" into a single pn_union
1304 * dependences with the union dependence relation.
1306 * If "dep2" is already a pn_union, we simply extend it.
1307 * Otherwise, we create a new pn_union modeled after "dep2",
1308 * add it to the list of dependences and turn "dep2" into a pn_part.
1309 * "dep1" is turned into a pn_part in any case.
1311 static void merge_dependences(PDG *pdg, pdg::dependence *dep1,
1312 pdg::dependence *dep2)
1314 pdg::dependence *dep_union;
1316 if (dep2->type == pdg::dependence::pn_union)
1317 dep_union = dep2;
1318 else {
1319 pdg::IslMap *rel;
1320 dep_union = new pdg::dependence;
1321 dep_union->from = dep2->from;
1322 dep_union->to = dep2->to;
1323 dep_union->from_access = dep2->from_access;
1324 dep_union->to_access = NULL;
1325 dep_union->array = dep2->array;
1326 dep_union->type = pdg::dependence::pn_union;
1327 rel = dep2->relation;
1328 dep_union->relation = new pdg::IslMap(rel->get_isl_map());
1329 pdg->dependences.push_back(dep_union);
1331 dep2->type = pdg::dependence::pn_part;
1332 dep2->container = dep_union;
1335 dep1->type = pdg::dependence::pn_part;
1336 dep1->container = dep_union;
1338 dep_union->relation->map = isl_map_union(dep_union->relation->map,
1339 dep1->relation->get_isl_map());
1342 /* Try and merge dependences between a given pair of (distinct) nodes.
1343 * A merge is performed only if it the resulting merged dependence
1344 * does not exhibit any reordering.
1345 * The merging needs to be applied before the buffer size computation
1346 * as the buffer sizes are computed on the merged (pn_union) dependences.
1348 * We run through all original dependences and check whether it can
1349 * be combined with any later dependences. If so, we turn the two
1350 * dependences into "pn_part"s and add an extra pn_union dependence
1351 * that combines the two. The inner loop starts from the latest
1352 * dependence so that we compare with any previously added pn_union
1353 * dependences first. If such a previously add pn_union can be combined
1354 * with the current dependence, it is simply extended to include the
1355 * current dependence.
1357 * We currently don't allow any merging of dependences involving control.
1359 * If the user has turned off merging, the we do nothing.
1360 * We do the same if the user has turned off reuse detection, as there
1361 * may in this case be dependences with multiplicity. It is not clear
1362 * if we would want to merge such edges.
1364 static void merge_dependences(PDG *pdg, struct pn_options *options)
1366 int n_dep;
1368 if (!options->reuse)
1369 return;
1370 if (!options->merge)
1371 return;
1373 n_dep = pdg->dependences.size();
1374 for (int i = 0; i < n_dep; ++i) {
1375 pdg::dependence *dep_i = pdg->dependences[i];
1376 if (dep_i->type != pdg::dependence::flow)
1377 continue;
1378 if (dep_i->to == dep_i->from)
1379 continue;
1380 if (dep_i->controlled_relation)
1381 continue;
1383 for (int j = pdg->dependences.size() - 1; j > i; --j) {
1384 pdg::dependence *dep_j = pdg->dependences[j];
1386 if (dep_j->type != pdg::dependence::flow &&
1387 dep_j->type != pdg::dependence::pn_union)
1388 continue;
1389 if (dep_j->controlled_relation)
1390 continue;
1391 if (!can_merge(pdg, dep_i, dep_j))
1392 continue;
1394 merge_dependences(pdg, dep_i, dep_j);
1399 /* Is "access" one of the filter accesses of "node"?
1401 static bool is_filter_access(pdg::node *node, pdg::access *access)
1403 for (int i = 0; i < node->filters.size(); ++i) {
1404 pdg::call_or_access *coa;
1406 coa = node->filters[i];
1407 assert(coa->type == pdg::call_or_access::t_access);
1408 if (access == coa->access)
1409 return true;
1411 return false;
1414 /* Given the (overapproximation of the) dependence relation "dep_rel",
1415 * check whether "to" and "from" represent the same filter, i.e.,
1416 * whether they refer to the same array element written at the same
1417 * iteration.
1419 * We apply the mappings from source/sink iterations
1420 * to filter access relations to both sides of "dep_rel".
1421 * If the result is a subset of the identity relation, then
1422 * we know that the filter element accessed by the source is
1423 * exactly the same as the filter element accessed by
1424 * the courresponding sink(s).
1426 * If we were unable to find the source for one or both of the two filters,
1427 * then the filter access relations live in different spaces and
1428 * the computed relation cannot be a subset of the identity relation.
1430 static bool is_same_filter(pdg::access *to, pdg::access *from,
1431 __isl_keep isl_map *dep_rel)
1433 isl_union_map *from_access;
1434 isl_union_map *to_access;
1435 isl_union_map *test;
1436 isl_union_map *univ;
1437 isl_union_map *id;
1438 bool same;
1440 if (to->array != from->array)
1441 return false;
1443 from_access = from->extract_access_map();
1444 to_access = to->extract_access_map();
1445 test = isl_union_map_from_map(isl_map_copy(dep_rel));
1446 test = isl_union_map_apply_domain(test, from_access);
1447 test = isl_union_map_apply_range(test, to_access);
1448 univ = isl_union_map_universe(isl_union_map_copy(test));
1449 id = isl_union_set_identity(isl_union_map_domain(univ));
1450 same = isl_union_map_is_subset(test, id);
1451 isl_union_map_free(test);
1452 isl_union_map_free(id);
1454 return same;
1457 /* Insert equalities between source filters and sink filters
1458 * of dependences, whenever we are able to detect that they are the same.
1460 * We first introduce the constraints on the sink filters in the dependence
1461 * relation and we add unconstrained variables for the source filters.
1462 * Then, for each of the sink filters, we check if we can find
1463 * any source filter that has the same value on the other side
1464 * of the dependence. If so, we can keep the constraints on this
1465 * filter value and we add an equality between the source filter
1466 * and the sink filter so that these constraints will also be
1467 * applied to the source filter.
1468 * Otherwise, we eliminate the sink filter value from the constraints.
1470 static void insert_filter_constraints(pdg::dependence *dep)
1472 isl_space *space;
1473 isl_map *map;
1474 isl_map *dep_rel;
1475 int n_in;
1476 int n_out;
1477 bool any = false;
1479 dep_rel = isl_map_copy(dep->relation->map);
1480 n_in = isl_map_dim(dep_rel, isl_dim_in);
1481 n_out = isl_map_dim(dep_rel, isl_dim_out);
1483 space = isl_set_get_space(dep->from->source->set);
1484 map = isl_set_unwrap(isl_set_universe(space));
1485 map = isl_map_reverse(isl_map_domain_map(map));
1486 dep_rel = isl_map_apply_domain(dep_rel, map);
1487 map = isl_set_unwrap(dep->to->source->get_isl_set());
1488 map = isl_map_reverse(isl_map_domain_map(map));
1489 dep_rel = isl_map_apply_range(dep_rel, map);
1491 for (int i = 0; i < dep->to->filters.size(); ++i) {
1492 pdg::call_or_access *coa_i;
1493 pdg::access *access_i;
1494 bool found = false;
1496 coa_i = dep->to->filters[i];
1497 assert(coa_i->type == pdg::call_or_access::t_access);
1498 access_i = coa_i->access;
1500 for (int j = 0; j < dep->from->filters.size(); ++j) {
1501 pdg::call_or_access *coa_j;
1502 pdg::access *access_j;
1504 coa_j = dep->from->filters[j];
1505 assert(coa_j->type == pdg::call_or_access::t_access);
1506 access_j = coa_j->access;
1508 if (!is_same_filter(access_i, access_j,
1509 dep->relation->map))
1510 continue;
1511 dep_rel = isl_map_equate(dep_rel, isl_dim_in, n_in + j,
1512 isl_dim_out, n_out + i);
1513 found = true;
1514 any = true;
1517 if (!found)
1518 dep_rel = isl_map_eliminate(dep_rel, isl_dim_out,
1519 n_out + i, 1);
1522 if (any) {
1523 isl_map_free(dep->relation->map);
1524 dep->relation->map = dep_rel;
1525 } else
1526 isl_map_free(dep_rel);
1529 /* Insert equalities between source filters and sink filters
1530 * of dependences, whenever we are able to detect that they are the same.
1532 * We currently don't introduce any such equalities in dependences
1533 * that involve control variables. Both these control variables and
1534 * the filters will be treated as "dynamic controls" in pn2adg
1535 * and it probably needs to be tweaked to be able to handle two sets
1536 * of dynamic controls.
1538 static void insert_filter_constraints(PDG *pdg)
1540 for (int i = 0; i < pdg->dependences.size(); ++i) {
1541 pdg::dependence *dep = pdg->dependences[i];
1543 if (dep->type == pdg::dependence::uninitialized)
1544 continue;
1545 if (dep->to == dep->from)
1546 continue;
1547 if (dep->controlled_relation)
1548 continue;
1549 if (dep->to->filters.size() == 0)
1550 continue;
1551 if (dep->from->filters.size() == 0)
1552 continue;
1553 if (is_filter_access(dep->to, dep->to_access))
1554 continue;
1555 insert_filter_constraints(dep);
1559 int main(int argc, char * argv[])
1561 isl_ctx *ctx;
1562 FILE *in = stdin, *out = stdout;
1563 int c, ind = 0;
1564 PDG *pdg;
1565 struct pn_options *options = pn_options_new_with_defaults();
1566 bool evaluate = true;
1568 argc = pn_options_parse(options, argc, argv, ISL_ARG_ALL);
1570 if (!options->reuse)
1571 options->propagate = 0;
1573 if (options->input && strcmp(options->input, "-")) {
1574 in = fopen(options->input, "r");
1575 assert(in);
1576 if (!options->output) {
1577 int len = strlen(options->input);
1578 if (len > 5 && !strcmp(options->input+len-5, ".yaml"))
1579 len -= 5;
1580 options->output = (char *)malloc(len+9+1);
1581 strncpy(options->output, options->input, len);
1582 strcpy(options->output+len, options->reuse ? "_pn.yaml" : "_cpn.yaml");
1586 ctx = isl_ctx_alloc_with_options(&pn_options_args, options);
1587 pdg = PDG::Load(in, ctx);
1588 assert(pdg);
1589 int nparam = pdg->params.size();
1591 if (options->propagate)
1592 copy_propagation(pdg);
1594 compute_filter_sources(pdg);
1595 for (int i = 0; i < pdg->arrays.size(); ++i)
1596 find_deps(pdg, pdg->arrays[i], flow);
1597 extract_control_dependences(pdg);
1599 for (int i = 0; i < nparam; ++i)
1600 if (!pdg->params[i]->value) {
1601 evaluate = false;
1602 break;
1605 bool translated;
1606 if (options->reschedule) {
1607 common_dimension(pdg);
1608 translated = false;
1609 } else {
1610 set_schedule_from_prefix(pdg);
1611 translated = true;
1614 detect_reuse(pdg, options);
1615 split_multi_assignment(pdg);
1616 split_wires(pdg);
1617 merge_dependences(pdg, options);
1618 determine_dependence_properties(pdg, evaluate, translated, options);
1619 insert_filter_constraints(pdg);
1621 pdg->add_history_line("pn", argc, argv);
1623 if (options->output && strcmp(options->output, "-")) {
1624 out = fopen(options->output, "w");
1625 assert(out);
1628 pdg->Dump(out);
1629 pdg->free();
1630 delete pdg;
1631 isl_ctx_free(ctx);
1633 return 0;