Mercurial > hg > CbC > CbC_gcc

annotate gcc/graphite-dependences.c @ 158:494b0b89df80 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
...
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Mon, 25 May 2020 18:13:55 +0900
parents 1830386684a0
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* Data dependence analysis for Graphite.
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
2 Copyright (C) 2009-2020 Free Software Foundation, Inc.
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 Konrad Trifunovic <konrad.trifunovic@inria.fr>.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 This file is part of GCC.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 GCC is free software; you can redistribute it and/or modify
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 it under the terms of the GNU General Public License as published by
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 the Free Software Foundation; either version 3, or (at your option)
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 any later version.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 GCC is distributed in the hope that it will be useful,
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 GNU General Public License for more details.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 You should have received a copy of the GNU General Public License
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 along with GCC; see the file COPYING3. If not see
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 <http://www.gnu.org/licenses/>. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
111
kono
parents: 67
diff changeset
22 #define USES_ISL
kono
parents: 67
diff changeset
23
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 #include "config.h"
111
kono
parents: 67
diff changeset
25
kono
parents: 67
diff changeset
26 #ifdef HAVE_isl
kono
parents: 67
diff changeset
27
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 #include "system.h"
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 #include "coretypes.h"
111
kono
parents: 67
diff changeset
30 #include "backend.h"
kono
parents: 67
diff changeset
31 #include "cfghooks.h"
kono
parents: 67
diff changeset
32 #include "tree.h"
kono
parents: 67
diff changeset
33 #include "gimple.h"
kono
parents: 67
diff changeset
34 #include "fold-const.h"
kono
parents: 67
diff changeset
35 #include "gimple-iterator.h"
kono
parents: 67
diff changeset
36 #include "tree-ssa-loop.h"
kono
parents: 67
diff changeset
37 #include "tree-pass.h"
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 #include "cfgloop.h"
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 #include "tree-data-ref.h"
111
kono
parents: 67
diff changeset
40 #include "graphite.h"
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41
111
kono
parents: 67
diff changeset
42 /* Add the constraints from the set S to the domain of MAP. */
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43
111
kono
parents: 67
diff changeset
44 static isl_map *
kono
parents: 67
diff changeset
45 constrain_domain (isl_map *map, isl_set *s)
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 {
111
kono
parents: 67
diff changeset
47 isl_space *d = isl_map_get_space (map);
kono
parents: 67
diff changeset
48 isl_id *id = isl_space_get_tuple_id (d, isl_dim_in);
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49
111
kono
parents: 67
diff changeset
50 s = isl_set_set_tuple_id (s, id);
kono
parents: 67
diff changeset
51 isl_space_free (d);
kono
parents: 67
diff changeset
52 return isl_map_coalesce (isl_map_intersect_domain (map, s));
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54
111
kono
parents: 67
diff changeset
55 /* Constrain pdr->accesses with pdr->subscript_sizes and pbb->domain. */
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56
111
kono
parents: 67
diff changeset
57 static isl_map *
kono
parents: 67
diff changeset
58 add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb)
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 {
111
kono
parents: 67
diff changeset
60 isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses),
kono
parents: 67
diff changeset
61 isl_set_copy (pdr->subscript_sizes));
kono
parents: 67
diff changeset
62 x = isl_map_coalesce (x);
kono
parents: 67
diff changeset
63 return constrain_domain (x, isl_set_copy (pbb->domain));
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65
111
kono
parents: 67
diff changeset
66 /* Returns an isl description of all memory operations in SCOP. The memory
kono
parents: 67
diff changeset
67 reads are returned in READS and writes in MUST_WRITES and MAY_WRITES. */
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
69 static void
111
kono
parents: 67
diff changeset
70 scop_get_reads_and_writes (scop_p scop, isl_union_map *&reads,
kono
parents: 67
diff changeset
71 isl_union_map *&must_writes,
kono
parents: 67
diff changeset
72 isl_union_map *&may_writes)
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 {
111
kono
parents: 67
diff changeset
74 int i, j;
kono
parents: 67
diff changeset
75 poly_bb_p pbb;
kono
parents: 67
diff changeset
76 poly_dr_p pdr;
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77
111
kono
parents: 67
diff changeset
78 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
79 {
111
kono
parents: 67
diff changeset
80 FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) {
kono
parents: 67
diff changeset
81 if (pdr_read_p (pdr))
kono
parents: 67
diff changeset
82 {
kono
parents: 67
diff changeset
83 if (dump_file)
kono
parents: 67
diff changeset
84 {
kono
parents: 67
diff changeset
85 fprintf (dump_file, "Adding read to depedence graph: ");
kono
parents: 67
diff changeset
86 print_pdr (dump_file, pdr);
kono
parents: 67
diff changeset
87 }
kono
parents: 67
diff changeset
88 isl_union_map *um
kono
parents: 67
diff changeset
89 = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
kono
parents: 67
diff changeset
90 reads = isl_union_map_union (reads, um);
kono
parents: 67
diff changeset
91 if (dump_file)
kono
parents: 67
diff changeset
92 {
kono
parents: 67
diff changeset
93 fprintf (dump_file, "Reads depedence graph: ");
kono
parents: 67
diff changeset
94 print_isl_union_map (dump_file, reads);
kono
parents: 67
diff changeset
95 }
kono
parents: 67
diff changeset
96 }
kono
parents: 67
diff changeset
97 else if (pdr_write_p (pdr))
kono
parents: 67
diff changeset
98 {
kono
parents: 67
diff changeset
99 if (dump_file)
kono
parents: 67
diff changeset
100 {
kono
parents: 67
diff changeset
101 fprintf (dump_file, "Adding must write to depedence graph: ");
kono
parents: 67
diff changeset
102 print_pdr (dump_file, pdr);
kono
parents: 67
diff changeset
103 }
kono
parents: 67
diff changeset
104 isl_union_map *um
kono
parents: 67
diff changeset
105 = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
kono
parents: 67
diff changeset
106 must_writes = isl_union_map_union (must_writes, um);
kono
parents: 67
diff changeset
107 if (dump_file)
kono
parents: 67
diff changeset
108 {
kono
parents: 67
diff changeset
109 fprintf (dump_file, "Must writes depedence graph: ");
kono
parents: 67
diff changeset
110 print_isl_union_map (dump_file, must_writes);
kono
parents: 67
diff changeset
111 }
kono
parents: 67
diff changeset
112 }
kono
parents: 67
diff changeset
113 else if (pdr_may_write_p (pdr))
kono
parents: 67
diff changeset
114 {
kono
parents: 67
diff changeset
115 if (dump_file)
kono
parents: 67
diff changeset
116 {
kono
parents: 67
diff changeset
117 fprintf (dump_file, "Adding may write to depedence graph: ");
kono
parents: 67
diff changeset
118 print_pdr (dump_file, pdr);
kono
parents: 67
diff changeset
119 }
kono
parents: 67
diff changeset
120 isl_union_map *um
kono
parents: 67
diff changeset
121 = isl_union_map_from_map (add_pdr_constraints (pdr, pbb));
kono
parents: 67
diff changeset
122 may_writes = isl_union_map_union (may_writes, um);
kono
parents: 67
diff changeset
123 if (dump_file)
kono
parents: 67
diff changeset
124 {
kono
parents: 67
diff changeset
125 fprintf (dump_file, "May writes depedence graph: ");
kono
parents: 67
diff changeset
126 print_isl_union_map (dump_file, may_writes);
kono
parents: 67
diff changeset
127 }
kono
parents: 67
diff changeset
128 }
kono
parents: 67
diff changeset
129 }
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
130 }
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
132
111
kono
parents: 67
diff changeset
133 /* Helper function used on each MAP of a isl_union_map. Computes the
kono
parents: 67
diff changeset
134 maximal output dimension. */
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135
111
kono
parents: 67
diff changeset
136 static isl_stat
kono
parents: 67
diff changeset
137 max_number_of_out_dimensions (__isl_take isl_map *map, void *user)
kono
parents: 67
diff changeset
138 {
kono
parents: 67
diff changeset
139 int global_max = *((int *) user);
kono
parents: 67
diff changeset
140 isl_space *space = isl_map_get_space (map);
kono
parents: 67
diff changeset
141 int nb_out = isl_space_dim (space, isl_dim_out);
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
142
111
kono
parents: 67
diff changeset
143 if (global_max < nb_out)
kono
parents: 67
diff changeset
144 *((int *) user) = nb_out;
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145
111
kono
parents: 67
diff changeset
146 isl_map_free (map);
kono
parents: 67
diff changeset
147 isl_space_free (space);
kono
parents: 67
diff changeset
148 return isl_stat_ok;
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150
111
kono
parents: 67
diff changeset
151 /* Extends the output dimension of MAP to MAX dimensions. */
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
152
111
kono
parents: 67
diff changeset
153 static __isl_give isl_map *
kono
parents: 67
diff changeset
154 extend_map (__isl_take isl_map *map, int max)
kono
parents: 67
diff changeset
155 {
kono
parents: 67
diff changeset
156 isl_space *space = isl_map_get_space (map);
kono
parents: 67
diff changeset
157 int n = isl_space_dim (space, isl_dim_out);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
158
111
kono
parents: 67
diff changeset
159 isl_space_free (space);
kono
parents: 67
diff changeset
160 return isl_map_add_dims (map, isl_dim_out, max - n);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
161 }
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
162
111
kono
parents: 67
diff changeset
163 /* Structure used to pass parameters to extend_schedule_1. */
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
164
111
kono
parents: 67
diff changeset
165 struct extend_schedule_str {
kono
parents: 67
diff changeset
166 int max;
kono
parents: 67
diff changeset
167 isl_union_map *umap;
kono
parents: 67
diff changeset
168 };
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
169
111
kono
parents: 67
diff changeset
170 /* Helper function for extend_schedule. */
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
171
111
kono
parents: 67
diff changeset
172 static isl_stat
kono
parents: 67
diff changeset
173 extend_schedule_1 (__isl_take isl_map *map, void *user)
kono
parents: 67
diff changeset
174 {
kono
parents: 67
diff changeset
175 struct extend_schedule_str *str = (struct extend_schedule_str *) user;
kono
parents: 67
diff changeset
176 str->umap = isl_union_map_add_map (str->umap, extend_map (map, str->max));
kono
parents: 67
diff changeset
177 return isl_stat_ok;
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
178 }
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
179
111
kono
parents: 67
diff changeset
180 /* Return a relation that has uniform output dimensions. */
kono
parents: 67
diff changeset
181
kono
parents: 67
diff changeset
182 static __isl_give isl_union_map *
kono
parents: 67
diff changeset
183 extend_schedule (__isl_take isl_union_map *x)
kono
parents: 67
diff changeset
184 {
kono
parents: 67
diff changeset
185 int max = 0;
kono
parents: 67
diff changeset
186 struct extend_schedule_str str;
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
187
111
kono
parents: 67
diff changeset
188 isl_union_map_foreach_map (x, max_number_of_out_dimensions, (void *) &max);
kono
parents: 67
diff changeset
189 str.max = max;
kono
parents: 67
diff changeset
190 str.umap = isl_union_map_empty (isl_union_map_get_space (x));
kono
parents: 67
diff changeset
191 isl_union_map_foreach_map (x, extend_schedule_1, (void *) &str);
kono
parents: 67
diff changeset
192 isl_union_map_free (x);
kono
parents: 67
diff changeset
193 return isl_union_map_coalesce (str.umap);
kono
parents: 67
diff changeset
194 }
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
195
111
kono
parents: 67
diff changeset
196 /* Applies SCHEDULE to the in and out dimensions of the dependences
kono
parents: 67
diff changeset
197 DEPS and return the resulting relation. */
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
198
111
kono
parents: 67
diff changeset
199 static isl_map *
kono
parents: 67
diff changeset
200 apply_schedule_on_deps (__isl_keep isl_union_map *schedule,
kono
parents: 67
diff changeset
201 __isl_keep isl_union_map *deps)
kono
parents: 67
diff changeset
202 {
kono
parents: 67
diff changeset
203 isl_union_map *trans = extend_schedule (isl_union_map_copy (schedule));
kono
parents: 67
diff changeset
204 isl_union_map *ux = isl_union_map_copy (deps);
kono
parents: 67
diff changeset
205 ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans));
kono
parents: 67
diff changeset
206 ux = isl_union_map_apply_range (ux, trans);
kono
parents: 67
diff changeset
207 ux = isl_union_map_coalesce (ux);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
208
111
kono
parents: 67
diff changeset
209 if (!isl_union_map_is_empty (ux))
kono
parents: 67
diff changeset
210 return isl_map_from_union_map (ux);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
211
111
kono
parents: 67
diff changeset
212 isl_union_map_free (ux);
kono
parents: 67
diff changeset
213 return NULL;
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
214 }
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
215
111
kono
parents: 67
diff changeset
216 /* Return true when DEPS is non empty and the intersection of LEX with
kono
parents: 67
diff changeset
217 the DEPS transformed by SCHEDULE is non empty. LEX is the relation
kono
parents: 67
diff changeset
218 in which all the inputs before DEPTH occur at the same time as the
kono
parents: 67
diff changeset
219 output, and the input at DEPTH occurs before output. */
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
220
111
kono
parents: 67
diff changeset
221 bool
kono
parents: 67
diff changeset
222 carries_deps (__isl_keep isl_union_map *schedule,
kono
parents: 67
diff changeset
223 __isl_keep isl_union_map *deps,
kono
parents: 67
diff changeset
224 int depth)
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
225 {
111
kono
parents: 67
diff changeset
226 if (isl_union_map_is_empty (deps))
kono
parents: 67
diff changeset
227 return false;
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
228
111
kono
parents: 67
diff changeset
229 isl_map *x = apply_schedule_on_deps (schedule, deps);
kono
parents: 67
diff changeset
230 if (x == NULL)
kono
parents: 67
diff changeset
231 return false;
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
232
111
kono
parents: 67
diff changeset
233 isl_space *space = isl_map_get_space (x);
kono
parents: 67
diff changeset
234 isl_map *lex = isl_map_lex_le (isl_space_range (space));
kono
parents: 67
diff changeset
235 isl_constraint *ineq = isl_inequality_alloc
kono
parents: 67
diff changeset
236 (isl_local_space_from_space (isl_map_get_space (x)));
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
237
111
kono
parents: 67
diff changeset
238 for (int i = 0; i < depth - 1; i++)
kono
parents: 67
diff changeset
239 lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
240
111
kono
parents: 67
diff changeset
241 /* in + 1 <= out */
kono
parents: 67
diff changeset
242 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1);
kono
parents: 67
diff changeset
243 ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1);
kono
parents: 67
diff changeset
244 ineq = isl_constraint_set_constant_si (ineq, -1);
kono
parents: 67
diff changeset
245 lex = isl_map_add_constraint (lex, ineq);
kono
parents: 67
diff changeset
246 lex = isl_map_coalesce (lex);
kono
parents: 67
diff changeset
247 x = isl_map_intersect (x, lex);
kono
parents: 67
diff changeset
248 bool res = !isl_map_is_empty (x);
67
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
249
111
kono
parents: 67
diff changeset
250 isl_map_free (x);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
251 return res;
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
252 }
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
253
111
kono
parents: 67
diff changeset
254 /* Compute the dependence relations for the SCOP:
kono
parents: 67
diff changeset
255 RAW are read after write dependences,
kono
parents: 67
diff changeset
256 WAR are write after read dependences,
kono
parents: 67
diff changeset
257 WAW are write after write dependences. */
67
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
258
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
259 void
111
kono
parents: 67
diff changeset
260 scop_get_dependences (scop_p scop)
67
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
261 {
111
kono
parents: 67
diff changeset
262 if (scop->dependence)
kono
parents: 67
diff changeset
263 return;
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
264
111
kono
parents: 67
diff changeset
265 isl_space *space = isl_set_get_space (scop->param_context);
kono
parents: 67
diff changeset
266 isl_union_map *reads = isl_union_map_empty (isl_space_copy (space));
kono
parents: 67
diff changeset
267 isl_union_map *must_writes = isl_union_map_empty (isl_space_copy (space));
kono
parents: 67
diff changeset
268 isl_union_map *may_writes = isl_union_map_empty (space);
kono
parents: 67
diff changeset
269 scop_get_reads_and_writes (scop, reads, must_writes, may_writes);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
270
111
kono
parents: 67
diff changeset
271 if (dump_file)
kono
parents: 67
diff changeset
272 {
kono
parents: 67
diff changeset
273 fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n");
kono
parents: 67
diff changeset
274 fprintf (dump_file, "Statements on the iteration domain are mapped to"
kono
parents: 67
diff changeset
275 " array references.\n");
kono
parents: 67
diff changeset
276 fprintf (dump_file, " To read the following data references:\n\n");
kono
parents: 67
diff changeset
277 fprintf (dump_file, " S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n");
kono
parents: 67
diff changeset
278 fprintf (dump_file, " S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n");
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
279
111
kono
parents: 67
diff changeset
280 fprintf (dump_file, " S_5[i0] is the dynamic instance of statement"
kono
parents: 67
diff changeset
281 " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n");
kono
parents: 67
diff changeset
282 fprintf (dump_file, " [1, i0] is a 'memref' with alias set 1"
kono
parents: 67
diff changeset
283 " and first subscript access i0.\n");
kono
parents: 67
diff changeset
284 fprintf (dump_file, " [106] is a 'scalar reference' which is the sum of"
kono
parents: 67
diff changeset
285 " SSA_NAME_VERSION 6"
kono
parents: 67
diff changeset
286 " and --param graphite-max-arrays-per-scop=100\n");
kono
parents: 67
diff changeset
287 fprintf (dump_file, "-----------------------\n\n");
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
288
111
kono
parents: 67
diff changeset
289 fprintf (dump_file, "data references (\n");
kono
parents: 67
diff changeset
290 fprintf (dump_file, " reads: ");
kono
parents: 67
diff changeset
291 print_isl_union_map (dump_file, reads);
kono
parents: 67
diff changeset
292 fprintf (dump_file, " must_writes: ");
kono
parents: 67
diff changeset
293 print_isl_union_map (dump_file, must_writes);
kono
parents: 67
diff changeset
294 fprintf (dump_file, " may_writes: ");
kono
parents: 67
diff changeset
295 print_isl_union_map (dump_file, may_writes);
kono
parents: 67
diff changeset
296 fprintf (dump_file, ")\n");
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
297 }
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
298
111
kono
parents: 67
diff changeset
299 gcc_assert (scop->original_schedule);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
300
111
kono
parents: 67
diff changeset
301 isl_union_access_info *ai;
kono
parents: 67
diff changeset
302 ai = isl_union_access_info_from_sink (isl_union_map_copy (reads));
kono
parents: 67
diff changeset
303 ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes));
kono
parents: 67
diff changeset
304 ai = isl_union_access_info_set_may_source (ai, may_writes);
kono
parents: 67
diff changeset
305 ai = isl_union_access_info_set_schedule
kono
parents: 67
diff changeset
306 (ai, isl_schedule_copy (scop->original_schedule));
kono
parents: 67
diff changeset
307 isl_union_flow *flow = isl_union_access_info_compute_flow (ai);
kono
parents: 67
diff changeset
308 isl_union_map *raw = isl_union_flow_get_must_dependence (flow);
kono
parents: 67
diff changeset
309 isl_union_flow_free (flow);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
310
111
kono
parents: 67
diff changeset
311 ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes));
kono
parents: 67
diff changeset
312 ai = isl_union_access_info_set_must_source (ai, must_writes);
kono
parents: 67
diff changeset
313 ai = isl_union_access_info_set_may_source (ai, reads);
kono
parents: 67
diff changeset
314 ai = isl_union_access_info_set_schedule
kono
parents: 67
diff changeset
315 (ai, isl_schedule_copy (scop->original_schedule));
kono
parents: 67
diff changeset
316 flow = isl_union_access_info_compute_flow (ai);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
317
111
kono
parents: 67
diff changeset
318 isl_union_map *waw = isl_union_flow_get_must_dependence (flow);
kono
parents: 67
diff changeset
319 isl_union_map *war = isl_union_flow_get_may_dependence (flow);
kono
parents: 67
diff changeset
320 war = isl_union_map_subtract (war, isl_union_map_copy (waw));
kono
parents: 67
diff changeset
321 isl_union_flow_free (flow);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
322
111
kono
parents: 67
diff changeset
323 raw = isl_union_map_coalesce (raw);
kono
parents: 67
diff changeset
324 waw = isl_union_map_coalesce (waw);
kono
parents: 67
diff changeset
325 war = isl_union_map_coalesce (war);
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
326
111
kono
parents: 67
diff changeset
327 isl_union_map *dependences = raw;
kono
parents: 67
diff changeset
328 dependences = isl_union_map_union (dependences, war);
kono
parents: 67
diff changeset
329 dependences = isl_union_map_union (dependences, waw);
kono
parents: 67
diff changeset
330 dependences = isl_union_map_coalesce (dependences);
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
331
111
kono
parents: 67
diff changeset
332 if (dump_file)
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
333 {
111
kono
parents: 67
diff changeset
334 fprintf (dump_file, "data dependences (\n");
kono
parents: 67
diff changeset
335 print_isl_union_map (dump_file, dependences);
kono
parents: 67
diff changeset
336 fprintf (dump_file, ")\n");
63
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 55
diff changeset
337 }
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
338
111
kono
parents: 67
diff changeset
339 scop->dependence = dependences;
55
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
340 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
341
111
kono
parents: 67
diff changeset
342 #endif /* HAVE_isl */