Bug Summary

File:tools/polly/lib/External/isl/isl_lp.c
Warning:line 159, column 14
Dereference of null pointer

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_lp.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -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 -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/include -I /usr/include/jsoncpp -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.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-7~svn329677/build-llvm/tools/polly/lib/External -fdebug-prefix-map=/build/llvm-toolchain-snapshot-7~svn329677=. -ferror-limit 19 -fmessage-length 0 -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/isl_lp.c
1/*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 *
4 * Use of this software is governed by the MIT license
5 *
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
9
10#include <isl_ctx_private.h>
11#include <isl_map_private.h>
12#include <isl/lp.h>
13#include <isl_seq.h>
14#include "isl_tab.h"
15#include <isl_options_private.h>
16#include <isl_local_space_private.h>
17#include <isl_aff_private.h>
18#include <isl_mat_private.h>
19#include <isl_val_private.h>
20#include <isl_vec_private.h>
21
22#include <bset_to_bmap.c>
23#include <set_to_map.c>
24
25enum isl_lp_result isl_tab_solve_lp(__isl_keep isl_basic_map *bmap,
26 int maximize, isl_int *f, isl_int denom, isl_int *opt,
27 isl_int *opt_denom, __isl_give isl_vec **sol)
28{
29 struct isl_tab *tab;
30 enum isl_lp_result res;
31 unsigned dim = isl_basic_map_total_dim(bmap);
32
33 if (maximize)
34 isl_seq_neg(f, f, 1 + dim);
35
36 bmap = isl_basic_map_gauss(bmap, NULL((void*)0));
37 tab = isl_tab_from_basic_map(bmap, 0);
38 res = isl_tab_min(tab, f, denom, opt, opt_denom, 0);
39 if (res == isl_lp_ok && sol) {
40 *sol = isl_tab_get_sample_value(tab);
41 if (!*sol)
42 res = isl_lp_error;
43 }
44 isl_tab_free(tab);
45
46 if (maximize)
47 isl_seq_neg(f, f, 1 + dim);
48 if (maximize && opt)
49 isl_int_neg(*opt, *opt)isl_sioimath_neg((*opt), *(*opt));
50
51 return res;
52}
53
54/* Given a basic map "bmap" and an affine combination of the variables "f"
55 * with denominator "denom", set *opt / *opt_denom to the minimal
56 * (or maximal if "maximize" is true) value attained by f/d over "bmap",
57 * assuming the basic map is not empty and the expression cannot attain
58 * arbitrarily small (or large) values.
59 * If opt_denom is NULL, then *opt is rounded up (or down)
60 * to the nearest integer.
61 * The return value reflects the nature of the result (empty, unbounded,
62 * minimal or maximal value returned in *opt).
63 */
64enum isl_lp_result isl_basic_map_solve_lp(__isl_keep isl_basic_map *bmap,
65 int max, isl_int *f, isl_int d, isl_int *opt, isl_int *opt_denom,
66 __isl_give isl_vec **sol)
67{
68 if (sol)
69 *sol = NULL((void*)0);
70
71 if (!bmap)
72 return isl_lp_error;
73
74 return isl_tab_solve_lp(bmap, max, f, d, opt, opt_denom, sol);
75}
76
77enum isl_lp_result isl_basic_set_solve_lp(struct isl_basic_setisl_basic_map *bset, int max,
78 isl_int *f, isl_int d, isl_int *opt,
79 isl_int *opt_denom,
80 struct isl_vec **sol)
81{
82 return isl_basic_map_solve_lp(bset_to_bmap(bset), max,
83 f, d, opt, opt_denom, sol);
84}
85
86enum isl_lp_result isl_map_solve_lp(__isl_keep isl_map *map, int max,
87 isl_int *f, isl_int d, isl_int *opt,
88 isl_int *opt_denom,
89 struct isl_vec **sol)
90{
91 int i;
92 isl_int o;
93 isl_int t;
94 isl_int opt_i;
95 isl_int opt_denom_i;
96 enum isl_lp_result res;
97 int max_div;
98 isl_vec *v = NULL((void*)0);
99
100 if (!map)
3
Assuming 'map' is non-null
4
Taking false branch
101 return isl_lp_error;
102 if (map->n == 0)
5
Assuming the condition is false
6
Taking false branch
103 return isl_lp_empty;
104
105 max_div = 0;
106 for (i = 0; i < map->n; ++i)
7
Assuming the condition is true
8
Loop condition is true. Entering loop body
11
Assuming the condition is true
12
Loop condition is true. Entering loop body
15
Assuming the condition is false
16
Loop condition is false. Execution continues on line 109
107 if (map->p[i]->n_div > max_div)
9
Assuming the condition is false
10
Taking false branch
13
Assuming the condition is false
14
Taking false branch
108 max_div = map->p[i]->n_div;
109 if (max_div > 0) {
17
Taking false branch
110 unsigned total = isl_space_dim(map->dim, isl_dim_all);
111 v = isl_vec_alloc(map->ctx, 1 + total + max_div);
112 if (!v)
113 return isl_lp_error;
114 isl_seq_cpy(v->el, f, 1 + total);
115 isl_seq_clr(v->el + 1 + total, max_div);
116 f = v->el;
117 }
118
119 if (!opt && map->n > 1 && sol) {
18
Assuming 'opt' is null
19
Assuming 'sol' is null
20
Taking false branch
120 isl_int_init(o)isl_sioimath_init((o));
121 opt = &o;
122 }
123 if (map->n > 0)
21
Taking true branch
124 isl_int_init(opt_i)isl_sioimath_init((opt_i));
125 if (map->n > 0 && opt_denom) {
22
Assuming 'opt_denom' is null
23
Taking false branch
126 isl_int_init(opt_denom_i)isl_sioimath_init((opt_denom_i));
127 isl_int_init(t)isl_sioimath_init((t));
128 }
129
130 res = isl_basic_map_solve_lp(map->p[0], max, f, d,
131 opt, opt_denom, sol);
132 if (res == isl_lp_error || res == isl_lp_unbounded)
24
Assuming 'res' is not equal to isl_lp_error
25
Assuming 'res' is not equal to isl_lp_unbounded
26
Taking false branch
133 goto done;
134
135 if (sol)
27
Taking false branch
136 *sol = NULL((void*)0);
137
138 for (i = 1; i < map->n; ++i) {
28
Loop condition is true. Entering loop body
139 isl_vec *sol_i = NULL((void*)0);
140 enum isl_lp_result res_i;
141 int better;
142
143 res_i = isl_basic_map_solve_lp(map->p[i], max, f, d,
144 &opt_i,
145 opt_denom ? &opt_denom_i : NULL((void*)0),
29
'?' condition is false
146 sol ? &sol_i : NULL((void*)0));
30
'?' condition is false
147 if (res_i == isl_lp_error || res_i == isl_lp_unbounded) {
31
Assuming 'res_i' is not equal to isl_lp_error
32
Assuming 'res_i' is not equal to isl_lp_unbounded
33
Taking false branch
148 res = res_i;
149 goto done;
150 }
151 if (res_i == isl_lp_empty)
34
Assuming 'res_i' is not equal to isl_lp_empty
35
Taking false branch
152 continue;
153 if (res == isl_lp_empty) {
36
Assuming 'res' is not equal to isl_lp_empty
37
Taking false branch
154 better = 1;
155 } else if (!opt_denom) {
38
Taking true branch
156 if (max)
39
Assuming 'max' is 0
40
Taking false branch
157 better = isl_int_gt(opt_i, *opt)(isl_sioimath_cmp(*(opt_i), *(*opt)) > 0);
158 else
159 better = isl_int_lt(opt_i, *opt)(isl_sioimath_cmp(*(opt_i), *(*opt)) < 0);
41
Within the expansion of the macro 'isl_int_lt':
a
Dereference of null pointer
160 } else {
161 isl_int_mul(t, opt_i, *opt_denom)isl_sioimath_mul((t), *(opt_i), *(*opt_denom));
162 isl_int_submul(t, *opt, opt_denom_i)isl_sioimath_submul((t), *(*opt), *(opt_denom_i));
163 if (max)
164 better = isl_int_is_pos(t)(isl_sioimath_sgn(*(t)) > 0);
165 else
166 better = isl_int_is_neg(t)(isl_sioimath_sgn(*(t)) < 0);
167 }
168 if (better) {
169 res = res_i;
170 if (opt)
171 isl_int_set(*opt, opt_i)isl_sioimath_set((*opt), *(opt_i));
172 if (opt_denom)
173 isl_int_set(*opt_denom, opt_denom_i)isl_sioimath_set((*opt_denom), *(opt_denom_i));
174 if (sol) {
175 isl_vec_free(*sol);
176 *sol = sol_i;
177 }
178 } else
179 isl_vec_free(sol_i);
180 }
181
182done:
183 isl_vec_free(v);
184 if (map->n > 0 && opt_denom) {
185 isl_int_clear(opt_denom_i)isl_sioimath_clear((opt_denom_i));
186 isl_int_clear(t)isl_sioimath_clear((t));
187 }
188 if (map->n > 0)
189 isl_int_clear(opt_i)isl_sioimath_clear((opt_i));
190 if (opt == &o)
191 isl_int_clear(o)isl_sioimath_clear((o));
192 return res;
193}
194
195enum isl_lp_result isl_set_solve_lp(__isl_keep isl_setisl_map *set, int max,
196 isl_int *f, isl_int d, isl_int *opt,
197 isl_int *opt_denom,
198 struct isl_vec **sol)
199{
200 return isl_map_solve_lp(set_to_map(set), max,
2
Calling 'isl_map_solve_lp'
201 f, d, opt, opt_denom, sol);
1
Passing value via 5th parameter 'opt'
202}
203
204/* Return the optimal (rational) value of "obj" over "bset", assuming
205 * that "obj" and "bset" have aligned parameters and divs.
206 * If "max" is set, then the maximal value is computed.
207 * Otherwise, the minimal value is computed.
208 *
209 * Return infinity or negative infinity if the optimal value is unbounded and
210 * NaN if "bset" is empty.
211 *
212 * Call isl_basic_set_solve_lp and translate the results.
213 */
214static __isl_give isl_val *basic_set_opt_lp(
215 __isl_keep isl_basic_setisl_basic_map *bset, int max, __isl_keep isl_aff *obj)
216{
217 isl_ctx *ctx;
218 isl_val *res;
219 enum isl_lp_result lp_res;
220
221 if (!bset || !obj)
222 return NULL((void*)0);
223
224 ctx = isl_aff_get_ctx(obj);
225 res = isl_val_alloc(ctx);
226 if (!res)
227 return NULL((void*)0);
228 lp_res = isl_basic_set_solve_lp(bset, max, obj->v->el + 1,
229 obj->v->el[0], &res->n, &res->d, NULL((void*)0));
230 if (lp_res == isl_lp_ok)
231 return isl_val_normalize(res);
232 isl_val_free(res);
233 if (lp_res == isl_lp_error)
234 return NULL((void*)0);
235 if (lp_res == isl_lp_empty)
236 return isl_val_nan(ctx);
237 if (max)
238 return isl_val_infty(ctx);
239 else
240 return isl_val_neginfty(ctx);
241}
242
243/* Return the optimal (rational) value of "obj" over "bset", assuming
244 * that "obj" and "bset" have aligned parameters.
245 * If "max" is set, then the maximal value is computed.
246 * Otherwise, the minimal value is computed.
247 *
248 * Return infinity or negative infinity if the optimal value is unbounded and
249 * NaN if "bset" is empty.
250 *
251 * Align the divs of "bset" and "obj" and call basic_set_opt_lp.
252 */
253static __isl_give isl_val *isl_basic_set_opt_lp_val_aligned(
254 __isl_keep isl_basic_setisl_basic_map *bset, int max, __isl_keep isl_aff *obj)
255{
256 int *exp1 = NULL((void*)0);
257 int *exp2 = NULL((void*)0);
258 isl_ctx *ctx;
259 isl_mat *bset_div = NULL((void*)0);
260 isl_mat *div = NULL((void*)0);
261 isl_val *res;
262 int bset_n_div, obj_n_div;
263
264 if (!bset || !obj)
265 return NULL((void*)0);
266
267 ctx = isl_aff_get_ctx(obj);
268 if (!isl_space_is_equal(bset->dim, obj->ls->dim))
269 isl_die(ctx, isl_error_invalid,do { isl_handle_error(ctx, isl_error_invalid, "spaces don't match"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/isl_lp.c"
, 270); return ((void*)0); } while (0)
270 "spaces don't match", return NULL)do { isl_handle_error(ctx, isl_error_invalid, "spaces don't match"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/isl_lp.c"
, 270); return ((void*)0); } while (0)
;
271
272 bset_n_div = isl_basic_set_dim(bset, isl_dim_div);
273 obj_n_div = isl_aff_dim(obj, isl_dim_div);
274 if (bset_n_div == 0 && obj_n_div == 0)
275 return basic_set_opt_lp(bset, max, obj);
276
277 bset = isl_basic_set_copy(bset);
278 obj = isl_aff_copy(obj);
279
280 bset_div = isl_basic_set_get_divs(bset);
281 exp1 = isl_alloc_array(ctx, int, bset_n_div)((int *)isl_malloc_or_die(ctx, (bset_n_div)*sizeof(int)));
282 exp2 = isl_alloc_array(ctx, int, obj_n_div)((int *)isl_malloc_or_die(ctx, (obj_n_div)*sizeof(int)));
283 if (!bset_div || (bset_n_div && !exp1) || (obj_n_div && !exp2))
284 goto error;
285
286 div = isl_merge_divs(bset_div, obj->ls->div, exp1, exp2);
287
288 bset = isl_basic_set_expand_divs(bset, isl_mat_copy(div), exp1);
289 obj = isl_aff_expand_divs(obj, isl_mat_copy(div), exp2);
290
291 res = basic_set_opt_lp(bset, max, obj);
292
293 isl_mat_free(bset_div);
294 isl_mat_free(div);
295 free(exp1);
296 free(exp2);
297 isl_basic_set_free(bset);
298 isl_aff_free(obj);
299
300 return res;
301error:
302 isl_mat_free(div);
303 isl_mat_free(bset_div);
304 free(exp1);
305 free(exp2);
306 isl_basic_set_free(bset);
307 isl_aff_free(obj);
308 return NULL((void*)0);
309}
310
311/* Return the optimal (rational) value of "obj" over "bset".
312 * If "max" is set, then the maximal value is computed.
313 * Otherwise, the minimal value is computed.
314 *
315 * Return infinity or negative infinity if the optimal value is unbounded and
316 * NaN if "bset" is empty.
317 */
318static __isl_give isl_val *isl_basic_set_opt_lp_val(
319 __isl_keep isl_basic_setisl_basic_map *bset, int max, __isl_keep isl_aff *obj)
320{
321 isl_bool equal;
322 isl_val *res;
323
324 if (!bset || !obj)
325 return NULL((void*)0);
326
327 equal = isl_basic_set_space_has_equal_params(bset, obj->ls->dim);
328 if (equal < 0)
329 return NULL((void*)0);
330 if (equal)
331 return isl_basic_set_opt_lp_val_aligned(bset, max, obj);
332
333 bset = isl_basic_set_copy(bset);
334 obj = isl_aff_copy(obj);
335 bset = isl_basic_set_align_params(bset, isl_aff_get_domain_space(obj));
336 obj = isl_aff_align_params(obj, isl_basic_set_get_space(bset));
337
338 res = isl_basic_set_opt_lp_val_aligned(bset, max, obj);
339
340 isl_basic_set_free(bset);
341 isl_aff_free(obj);
342
343 return res;
344}
345
346/* Return the minimal (rational) value of "obj" over "bset".
347 *
348 * Return negative infinity if the minimal value is unbounded and
349 * NaN if "bset" is empty.
350 */
351__isl_give isl_val *isl_basic_set_min_lp_val(__isl_keep isl_basic_setisl_basic_map *bset,
352 __isl_keep isl_aff *obj)
353{
354 return isl_basic_set_opt_lp_val(bset, 0, obj);
355}
356
357/* Return the maximal (rational) value of "obj" over "bset".
358 *
359 * Return infinity if the maximal value is unbounded and
360 * NaN if "bset" is empty.
361 */
362__isl_give isl_val *isl_basic_set_max_lp_val(__isl_keep isl_basic_setisl_basic_map *bset,
363 __isl_keep isl_aff *obj)
364{
365 return isl_basic_set_opt_lp_val(bset, 1, obj);
366}