2 * Copyright 2010-2011 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
17 #include <isl/constraint.h>
21 /* Construct a map that maps a domain of dimensionality "len"
22 * to another domain of the same dimensionality such that
23 * coordinate "first" of the range is equal to the sum of the "wave_len"
24 * coordinates starting at "first" in the domain.
25 * The remaining coordinates in the range are equal to the corresponding ones
27 * "dim" prescribes the parameters.
29 __isl_give isl_map
*wavefront(__isl_take isl_dim
*dim
, int len
,
30 int first
, int wave_len
)
39 dim
= isl_dim_add(dim
, isl_dim_in
, len
);
40 dim
= isl_dim_add(dim
, isl_dim_out
, len
);
41 bmap
= isl_basic_map_universe(isl_dim_copy(dim
));
43 for (i
= 0; i
< len
; ++i
) {
47 c
= isl_equality_alloc(isl_dim_copy(dim
));
48 isl_int_set_si(v
, -1);
49 isl_constraint_set_coefficient(c
, isl_dim_in
, i
, v
);
51 isl_constraint_set_coefficient(c
, isl_dim_out
, i
, v
);
52 bmap
= isl_basic_map_add_constraint(bmap
, c
);
55 c
= isl_equality_alloc(isl_dim_copy(dim
));
56 isl_int_set_si(v
, -1);
57 for (i
= 0; i
< wave_len
; ++i
)
58 isl_constraint_set_coefficient(c
, isl_dim_in
, first
+ i
, v
);
60 isl_constraint_set_coefficient(c
, isl_dim_out
, first
, v
);
61 bmap
= isl_basic_map_add_constraint(bmap
, c
);
66 return isl_map_from_basic_map(bmap
);
69 /* Construct a map from a len-dimensional domain to
70 * a (len-n)-dimensional domain that projects out the n coordinates
72 * "dim" prescribes the parameters.
74 __isl_give isl_map
*project_out(__isl_take isl_dim
*dim
,
75 int len
, int first
, int n
)
84 dim
= isl_dim_add(dim
, isl_dim_in
, len
);
85 dim
= isl_dim_add(dim
, isl_dim_out
, len
- n
);
86 bmap
= isl_basic_map_universe(isl_dim_copy(dim
));
88 for (i
= 0, j
= 0; i
< len
; ++i
) {
89 if (i
>= first
&& i
< first
+ n
)
91 c
= isl_equality_alloc(isl_dim_copy(dim
));
92 isl_int_set_si(v
, -1);
93 isl_constraint_set_coefficient(c
, isl_dim_in
, i
, v
);
95 isl_constraint_set_coefficient(c
, isl_dim_out
, j
, v
);
96 bmap
= isl_basic_map_add_constraint(bmap
, c
);
103 return isl_map_from_basic_map(bmap
);
106 /* Construct a projection that maps a src_len dimensional domain
107 * to its first dst_len coordinates.
108 * "dim" prescribes the parameters.
110 __isl_give isl_map
*projection(__isl_take isl_dim
*dim
,
111 int src_len
, int dst_len
)
113 return project_out(dim
, src_len
, dst_len
, src_len
- dst_len
);
116 /* Extend "set" with unconstrained coordinates to a total length of "dst_len".
118 __isl_give isl_set
*extend(__isl_take isl_set
*set
, int dst_len
)
124 dim
= isl_set_get_dim(set
);
125 n_set
= isl_dim_size(dim
, isl_dim_set
);
126 dim
= isl_dim_drop(dim
, isl_dim_set
, 0, n_set
);
127 map
= projection(dim
, dst_len
, n_set
);
128 map
= isl_map_reverse(map
);
130 return isl_set_apply(set
, map
);
133 /* Extract the access in stmt->text starting at position identifier
134 * and of length identifier_len, and return a corresponding cuda_stmt_access.
136 * The access in C notation is first copied to "buffer" (which
137 * has been allocated by the caller and should be of sufficient size)
138 * and slightly modified to a map in isl notation.
139 * This string is then parsed by isl.
141 static struct cuda_stmt_access
*stmt_extract_access(struct cuda_stmt
*stmt
,
143 int identifier
, int identifier_len
, int index
, int index_len
)
147 unsigned nparam
= isl_set_dim(stmt
->domain
, isl_dim_param
);
148 unsigned nvar
= isl_set_dim(stmt
->domain
, isl_dim_set
);
149 isl_ctx
*ctx
= isl_set_get_ctx(stmt
->domain
);
150 struct cuda_stmt_access
*access
;
152 access
= isl_alloc_type(ctx
, struct cuda_stmt_access
);
154 access
->text_offset
= identifier
;
155 access
->text_len
= (index
- identifier
) + index_len
;
160 pos
+= sprintf(buffer
, "[");
161 for (i
= 0; i
< nparam
; ++i
) {
163 pos
+= sprintf(buffer
+ pos
, ",");
164 pos
+= sprintf(buffer
+ pos
, "%s",
165 isl_set_get_dim_name(stmt
->domain
, isl_dim_param
, i
));
167 pos
+= sprintf(buffer
+ pos
, "] -> { %s[",
168 isl_set_get_tuple_name(stmt
->domain
));
169 for (i
= 0; i
< nvar
; ++i
) {
171 pos
+= sprintf(buffer
+ pos
, ",");
172 pos
+= sprintf(buffer
+ pos
, "%s",
173 isl_set_get_dim_name(stmt
->domain
, isl_dim_set
, i
));
175 pos
+= sprintf(buffer
+ pos
, "] -> ");
176 memcpy(buffer
+ pos
, stmt
->text
+ identifier
, identifier_len
);
177 pos
+= identifier_len
;
178 pos
+= sprintf(buffer
+ pos
, "[");
179 for (i
= 1; i
< index_len
- 1; ++i
) {
180 if (stmt
->text
[index
+ i
] == ']') {
184 buffer
[pos
++] = stmt
->text
[index
+ i
];
186 pos
+= sprintf(buffer
+ pos
, "] }");
187 access
->access
= isl_map_read_from_str(ctx
, buffer
, -1);
192 /* Construct an access to the given iterator.
194 static struct cuda_stmt_access
*iterator_access(struct cuda_stmt
*stmt
,
195 int identifier
, int len
, int pos
)
197 isl_ctx
*ctx
= isl_set_get_ctx(stmt
->domain
);
198 struct cuda_stmt_access
*access
;
202 map
= isl_map_from_domain(isl_set_copy(stmt
->domain
));
203 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
204 c
= isl_equality_alloc(isl_map_get_dim(map
));
205 isl_constraint_set_coefficient_si(c
, isl_dim_in
, pos
, 1);
206 isl_constraint_set_coefficient_si(c
, isl_dim_out
, 0, -1);
207 map
= isl_map_add_constraint(map
, c
);
209 access
= isl_alloc_type(ctx
, struct cuda_stmt_access
);
211 access
->text_offset
= identifier
;
212 access
->text_len
= len
;
217 access
->access
= map
;
222 /* Check if the identifier matches one of the iterators and
223 * if so return an access to that iterator.
225 static struct cuda_stmt_access
*stmt_extract_iterator(struct cuda_stmt
*stmt
,
226 int identifier
, int len
)
229 unsigned n
= isl_set_dim(stmt
->domain
, isl_dim_set
);
231 for (i
= 0; i
< n
; ++i
) {
233 name
= isl_set_get_dim_name(stmt
->domain
, isl_dim_set
, i
);
234 if (!strncmp(name
, stmt
->text
+ identifier
, len
) &&
236 return iterator_access(stmt
, identifier
, len
, i
);
242 static int is_identifier(int c
)
244 return isalnum(c
) || c
== '_';
247 static int is_assignment(const char *text
, int pos
, int *compound
)
249 if (text
[pos
] != '=')
251 if (pos
> 0 && text
[pos
- 1] == '=')
253 if (text
[pos
+ 1] == '=')
255 if (pos
>= 1 && text
[pos
- 1] == '>' &&
256 !(pos
>= 2 && text
[pos
- 2] == '>'))
258 if (pos
>= 1 && text
[pos
- 1] == '<' &&
259 !(pos
>= 2 && text
[pos
- 2] == '<'))
262 *compound
= pos
>= 1 && strchr("+-*/%&|^<>", text
[pos
- 1]);
267 /* Extract accesses from stmt->text and store them in stmt->accesses.
268 * dim describes the parameters.
270 void stmt_extract_accesses(struct cuda_stmt
*stmt
)
273 size_t text_len
= strlen(stmt
->text
);
278 unsigned nparam
= isl_set_dim(stmt
->domain
, isl_dim_param
);
279 unsigned nvar
= isl_set_dim(stmt
->domain
, isl_dim_set
);
280 struct cuda_stmt_access
**next_access
= &stmt
->accesses
;
282 for (i
= 0; i
< nparam
; ++i
)
283 len
+= strlen(isl_set_get_dim_name(stmt
->domain
,
285 for (i
= 0; i
< nvar
; ++i
)
286 len
+= strlen(isl_set_get_dim_name(stmt
->domain
, isl_dim_set
, i
));
287 buffer
= isl_alloc_array(isl_set_get_ctx(stmt
->domain
), char, len
);
290 stmt
->accesses
= NULL
;
291 for (i
= 0; i
< text_len
; ++i
) {
292 if (identifier
< 0 && isalpha(stmt
->text
[i
])) {
295 } else if (identifier
>= 0 && end
< 0 &&
296 is_identifier(stmt
->text
[i
]))
298 else if (identifier
>= 0 && end
< 0 && isblank(stmt
->text
[i
]))
300 else if (identifier
>= 0 && end
>= 0 && isblank(stmt
->text
[i
]))
302 else if (identifier
>= 0 && stmt
->text
[i
] == '[') {
305 for (j
= i
+ 1; j
< text_len
; ++j
)
306 if (stmt
->text
[j
] == ']' &&
307 stmt
->text
[j
+ 1] != '[')
309 *next_access
= stmt_extract_access(stmt
, buffer
,
310 identifier
, end
- identifier
, i
, j
- i
+ 1);
311 next_access
= &(*next_access
)->next
;
312 end
= identifier
= -1;
314 } else if (identifier
>= 0) {
317 *next_access
= stmt_extract_iterator(stmt
, identifier
,
320 next_access
= &(*next_access
)->next
;
321 end
= identifier
= -1;
325 end
= identifier
= -1;
326 /* If we find an assignment and we have seen a single
327 * access, that access must be a write.
329 if (is_assignment(stmt
->text
, i
, &compound
) &&
330 stmt
->accesses
&& !stmt
->accesses
->next
) {
331 stmt
->accesses
->write
= 1;
333 stmt
->accesses
->read
= 0;