Bug Summary

File:polly/lib/External/isl/isl_stride.c
Warning:line 151, column 2
Value stored to 'pos' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name isl_stride.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-11/lib/clang/11.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=gnu99 -fconst-strings -fdebug-compilation-dir /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/tools/polly/lib/External -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/External/isl/isl_stride.c
1/*
2 * Copyright 2012-2013 Ecole Normale Superieure
3 *
4 * Use of this software is governed by the MIT license
5 *
6 * Written by Sven Verdoolaege,
7 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
8 */
9
10#include <isl/val.h>
11#include <isl_map_private.h>
12#include <isl_aff_private.h>
13#include <isl/constraint.h>
14#include <isl/set.h>
15
16/* Stride information about a specific set dimension.
17 * The values of the set dimension are equal to
18 * "offset" plus a multiple of "stride".
19 */
20struct isl_stride_info {
21 isl_val *stride;
22 isl_aff *offset;
23};
24
25/* Return the ctx to which "si" belongs.
26 */
27isl_ctx *isl_stride_info_get_ctx(__isl_keep isl_stride_info *si)
28{
29 if (!si)
30 return NULL((void*)0);
31
32 return isl_val_get_ctx(si->stride);
33}
34
35/* Free "si" and return NULL.
36 */
37__isl_null isl_stride_info *isl_stride_info_free(
38 __isl_take isl_stride_info *si)
39{
40 if (!si)
41 return NULL((void*)0);
42 isl_val_free(si->stride);
43 isl_aff_free(si->offset);
44 free(si);
45 return NULL((void*)0);
46}
47
48/* Construct an isl_stride_info object with given offset and stride.
49 */
50__isl_give isl_stride_info *isl_stride_info_alloc(
51 __isl_take isl_val *stride, __isl_take isl_aff *offset)
52{
53 struct isl_stride_info *si;
54
55 if (!stride || !offset)
56 goto error;
57 si = isl_alloc_type(isl_val_get_ctx(stride), struct isl_stride_info)((struct isl_stride_info *)isl_malloc_or_die(isl_val_get_ctx(
stride), sizeof(struct isl_stride_info)))
;
58 if (!si)
59 goto error;
60 si->stride = stride;
61 si->offset = offset;
62 return si;
63error:
64 isl_val_free(stride);
65 isl_aff_free(offset);
66 return NULL((void*)0);
67}
68
69/* Make a copy of "si" and return it.
70 */
71__isl_give isl_stride_info *isl_stride_info_copy(
72 __isl_keep isl_stride_info *si)
73{
74 if (!si)
75 return NULL((void*)0);
76
77 return isl_stride_info_alloc(isl_val_copy(si->stride),
78 isl_aff_copy(si->offset));
79}
80
81/* Return the stride of "si".
82 */
83__isl_give isl_val *isl_stride_info_get_stride(__isl_keep isl_stride_info *si)
84{
85 if (!si)
86 return NULL((void*)0);
87 return isl_val_copy(si->stride);
88}
89
90/* Return the offset of "si".
91 */
92__isl_give isl_aff *isl_stride_info_get_offset(__isl_keep isl_stride_info *si)
93{
94 if (!si)
95 return NULL((void*)0);
96 return isl_aff_copy(si->offset);
97}
98
99/* Information used inside detect_stride.
100 *
101 * "pos" is the set dimension at which the stride is being determined.
102 * "want_offset" is set if the offset should be computed.
103 * "found" is set if some stride was found already.
104 * "stride" and "offset" contain the (combined) stride and offset
105 * found so far and are NULL when "found" is not set.
106 * If "want_offset" is not set, then "offset" remains NULL.
107 */
108struct isl_detect_stride_data {
109 int pos;
110 int want_offset;
111 int found;
112 isl_val *stride;
113 isl_aff *offset;
114};
115
116/* Set the stride and offset of data->pos to the given
117 * value and expression.
118 *
119 * If we had already found a stride before, then the two strides
120 * are combined into a single stride.
121 *
122 * In particular, if the new stride information is of the form
123 *
124 * i = f + s (...)
125 *
126 * and the old stride information is of the form
127 *
128 * i = f2 + s2 (...)
129 *
130 * then we compute the extended gcd of s and s2
131 *
132 * a s + b s2 = g,
133 *
134 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
135 * and the second with t2 = a s1/g.
136 * This results in
137 *
138 * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
139 *
140 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
141 * is the combined stride.
142 */
143static isl_stat set_stride(struct isl_detect_stride_data *data,
144 __isl_take isl_val *stride, __isl_take isl_aff *offset)
145{
146 int pos;
147
148 if (!stride || !offset)
149 goto error;
150
151 pos = data->pos;
Value stored to 'pos' is never read
152
153 if (data->found) {
154 isl_val *stride2, *a, *b, *g;
155 isl_aff *offset2;
156
157 stride2 = data->stride;
158 g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),
159 &a, &b);
160 a = isl_val_mul(a, isl_val_copy(stride));
161 a = isl_val_div(a, isl_val_copy(g));
162 stride2 = isl_val_div(stride2, g);
163 b = isl_val_mul(b, isl_val_copy(stride2));
164 stride = isl_val_mul(stride, stride2);
165
166 if (!data->want_offset) {
167 isl_val_free(a);
168 isl_val_free(b);
169 } else {
170 offset2 = data->offset;
171 offset2 = isl_aff_scale_val(offset2, a);
172 offset = isl_aff_scale_val(offset, b);
173 offset = isl_aff_add(offset, offset2);
174 }
175 }
176
177 data->found = 1;
178 data->stride = stride;
179 if (data->want_offset)
180 data->offset = offset;
181 else
182 isl_aff_free(offset);
183 if (!data->stride || (data->want_offset && !data->offset))
184 return isl_stat_error;
185
186 return isl_stat_ok;
187error:
188 isl_val_free(stride);
189 isl_aff_free(offset);
190 return isl_stat_error;
191}
192
193/* Check if constraint "c" imposes any stride on dimension data->pos
194 * and, if so, update the stride information in "data".
195 *
196 * In order to impose a stride on the dimension, "c" needs to be an equality
197 * and it needs to involve the dimension. Note that "c" may also be
198 * a div constraint and thus an inequality that we cannot use.
199 *
200 * Let c be of the form
201 *
202 * h(p) + g * v * i + g * stride * f(alpha) = 0
203 *
204 * with h(p) an expression in terms of the parameters and other dimensions
205 * and f(alpha) an expression in terms of the existentially quantified
206 * variables.
207 *
208 * If "stride" is not zero and not one, then it represents a non-trivial stride
209 * on "i". We compute a and b such that
210 *
211 * a v + b stride = 1
212 *
213 * We have
214 *
215 * g v i = -h(p) + g stride f(alpha)
216 *
217 * a g v i = -a h(p) + g stride f(alpha)
218 *
219 * a g v i + b g stride i = -a h(p) + g stride * (...)
220 *
221 * g i = -a h(p) + g stride * (...)
222 *
223 * i = -a h(p)/g + stride * (...)
224 *
225 * The expression "-a h(p)/g" can therefore be used as offset.
226 */
227static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
228{
229 struct isl_detect_stride_data *data = user;
230 int i;
231 isl_size n_div;
232 isl_ctx *ctx;
233 isl_stat r = isl_stat_ok;
234 isl_val *v, *stride, *m;
235 isl_bool is_eq, relevant, has_stride;
236
237 is_eq = isl_constraint_is_equality(c);
238 relevant = isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1);
239 if (is_eq < 0 || relevant < 0)
240 goto error;
241 if (!is_eq || !relevant) {
242 isl_constraint_free(c);
243 return isl_stat_ok;
244 }
245
246 n_div = isl_constraint_dim(c, isl_dim_div);
247 if (n_div < 0)
248 goto error;
249 ctx = isl_constraint_get_ctx(c);
250 stride = isl_val_zero(ctx);
251 for (i = 0; i < n_div; ++i) {
252 v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
253 stride = isl_val_gcd(stride, v);
254 }
255
256 v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
257 m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
258 stride = isl_val_div(stride, isl_val_copy(m));
259 v = isl_val_div(v, isl_val_copy(m));
260
261 has_stride = isl_val_gt_si(stride, 1);
262 if (has_stride >= 0 && has_stride) {
263 isl_aff *aff;
264 isl_val *gcd, *a, *b;
265
266 gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
267 isl_val_free(gcd);
268 isl_val_free(b);
269
270 aff = isl_constraint_get_aff(c);
271 for (i = 0; i < n_div; ++i)
272 aff = isl_aff_set_coefficient_si(aff,
273 isl_dim_div, i, 0);
274 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
275 aff = isl_aff_remove_unused_divs(aff);
276 a = isl_val_neg(a);
277 aff = isl_aff_scale_val(aff, a);
278 aff = isl_aff_scale_down_val(aff, m);
279 r = set_stride(data, stride, aff);
280 } else {
281 isl_val_free(stride);
282 isl_val_free(m);
283 isl_val_free(v);
284 }
285
286 isl_constraint_free(c);
287 if (has_stride < 0)
288 return isl_stat_error;
289 return r;
290error:
291 isl_constraint_free(c);
292 return isl_stat_error;
293}
294
295/* Check if the constraints in "set" imply any stride on set dimension "pos" and
296 * store the results in data->stride and data->offset.
297 *
298 * In particular, compute the affine hull and then check if
299 * any of the constraints in the hull impose any stride on the dimension.
300 * If no such constraint can be found, then the offset is taken
301 * to be the zero expression and the stride is taken to be one.
302 */
303static void set_detect_stride(__isl_keep isl_setisl_map *set, int pos,
304 struct isl_detect_stride_data *data)
305{
306 isl_basic_setisl_basic_map *hull;
307
308 hull = isl_set_affine_hull(isl_set_copy(set));
309
310 data->pos = pos;
311 data->found = 0;
312 data->stride = NULL((void*)0);
313 data->offset = NULL((void*)0);
314 if (isl_basic_set_foreach_constraint(hull, &detect_stride, data) < 0)
315 goto error;
316
317 if (!data->found) {
318 data->stride = isl_val_one(isl_set_get_ctx(set));
319 if (data->want_offset) {
320 isl_space *space;
321 isl_local_space *ls;
322
323 space = isl_set_get_space(set);
324 ls = isl_local_space_from_space(space);
325 data->offset = isl_aff_zero_on_domain(ls);
326 }
327 }
328 isl_basic_set_free(hull);
329 return;
330error:
331 isl_basic_set_free(hull);
332 data->stride = isl_val_free(data->stride);
333 data->offset = isl_aff_free(data->offset);
334}
335
336/* Check if the constraints in "set" imply any stride on set dimension "pos" and
337 * return the results in the form of an offset and a stride.
338 */
339__isl_give isl_stride_info *isl_set_get_stride_info(__isl_keep isl_setisl_map *set,
340 int pos)
341{
342 struct isl_detect_stride_data data;
343
344 data.want_offset = 1;
345 set_detect_stride(set, pos, &data);
346
347 return isl_stride_info_alloc(data.stride, data.offset);
348}
349
350/* Check if the constraints in "set" imply any stride on set dimension "pos" and
351 * return this stride.
352 */
353__isl_give isl_val *isl_set_get_stride(__isl_keep isl_setisl_map *set, int pos)
354{
355 struct isl_detect_stride_data data;
356
357 data.want_offset = 0;
358 set_detect_stride(set, pos, &data);
359
360 return data.stride;
361}
362
363/* Check if the constraints in "map" imply any stride on output dimension "pos",
364 * independently of any other output dimensions, and
365 * return the results in the form of an offset and a stride.
366 *
367 * Convert the input to a set with only the input dimensions and
368 * the single output dimension such that it be passed to
369 * isl_set_get_stride_info and convert the result back to
370 * an expression defined over the domain of "map".
371 */
372__isl_give isl_stride_info *isl_map_get_range_stride_info(
373 __isl_keep isl_map *map, int pos)
374{
375 isl_stride_info *si;
376 isl_setisl_map *set;
377 isl_size n_in;
378
379 n_in = isl_map_dim(map, isl_dim_in);
380 if (n_in < 0)
381 return NULL((void*)0);
382 map = isl_map_copy(map);
383 map = isl_map_project_onto(map, isl_dim_out, pos, 1);
384 set = isl_map_wrap(map);
385 si = isl_set_get_stride_info(set, n_in);
386 isl_set_free(set);
387 if (!si)
388 return NULL((void*)0);
389 si->offset = isl_aff_domain_factor_domain(si->offset);
390 if (!si->offset)
391 return isl_stride_info_free(si);
392 return si;
393}