File: | tools/polly/lib/External/isl/isl_tab.c |
Location: | line 3045, column 15 |
Description: | Dereference of undefined pointer value |
1 | /* | |||
2 | * Copyright 2008-2009 Katholieke Universiteit Leuven | |||
3 | * Copyright 2013 Ecole Normale Superieure | |||
4 | * Copyright 2014 INRIA Rocquencourt | |||
5 | * | |||
6 | * Use of this software is governed by the MIT license | |||
7 | * | |||
8 | * Written by Sven Verdoolaege, K.U.Leuven, Departement | |||
9 | * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium | |||
10 | * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France | |||
11 | * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, | |||
12 | * B.P. 105 - 78153 Le Chesnay, France | |||
13 | */ | |||
14 | ||||
15 | #include <isl_ctx_private.h> | |||
16 | #include <isl_mat_private.h> | |||
17 | #include <isl_vec_private.h> | |||
18 | #include "isl_map_private.h" | |||
19 | #include "isl_tab.h" | |||
20 | #include <isl_seq.h> | |||
21 | #include <isl_config.h> | |||
22 | ||||
23 | /* | |||
24 | * The implementation of tableaus in this file was inspired by Section 8 | |||
25 | * of David Detlefs, Greg Nelson and James B. Saxe, "Simplify: a theorem | |||
26 | * prover for program checking". | |||
27 | */ | |||
28 | ||||
29 | struct isl_tab *isl_tab_alloc(struct isl_ctx *ctx, | |||
30 | unsigned n_row, unsigned n_var, unsigned M) | |||
31 | { | |||
32 | int i; | |||
33 | struct isl_tab *tab; | |||
34 | unsigned off = 2 + M; | |||
35 | ||||
36 | tab = isl_calloc_type(ctx, struct isl_tab)((struct isl_tab *)isl_calloc_or_die(ctx, 1, sizeof(struct isl_tab ))); | |||
37 | if (!tab) | |||
38 | return NULL((void*)0); | |||
39 | tab->mat = isl_mat_alloc(ctx, n_row, off + n_var); | |||
40 | if (!tab->mat) | |||
41 | goto error; | |||
42 | tab->var = isl_alloc_array(ctx, struct isl_tab_var, n_var)((struct isl_tab_var *)isl_malloc_or_die(ctx, (n_var)*sizeof( struct isl_tab_var))); | |||
43 | if (n_var && !tab->var) | |||
44 | goto error; | |||
45 | tab->con = isl_alloc_array(ctx, struct isl_tab_var, n_row)((struct isl_tab_var *)isl_malloc_or_die(ctx, (n_row)*sizeof( struct isl_tab_var))); | |||
46 | if (n_row && !tab->con) | |||
47 | goto error; | |||
48 | tab->col_var = isl_alloc_array(ctx, int, n_var)((int *)isl_malloc_or_die(ctx, (n_var)*sizeof(int))); | |||
49 | if (n_var && !tab->col_var) | |||
50 | goto error; | |||
51 | tab->row_var = isl_alloc_array(ctx, int, n_row)((int *)isl_malloc_or_die(ctx, (n_row)*sizeof(int))); | |||
52 | if (n_row && !tab->row_var) | |||
53 | goto error; | |||
54 | for (i = 0; i < n_var; ++i) { | |||
55 | tab->var[i].index = i; | |||
56 | tab->var[i].is_row = 0; | |||
57 | tab->var[i].is_nonneg = 0; | |||
58 | tab->var[i].is_zero = 0; | |||
59 | tab->var[i].is_redundant = 0; | |||
60 | tab->var[i].frozen = 0; | |||
61 | tab->var[i].negated = 0; | |||
62 | tab->col_var[i] = i; | |||
63 | } | |||
64 | tab->n_row = 0; | |||
65 | tab->n_con = 0; | |||
66 | tab->n_eq = 0; | |||
67 | tab->max_con = n_row; | |||
68 | tab->n_col = n_var; | |||
69 | tab->n_var = n_var; | |||
70 | tab->max_var = n_var; | |||
71 | tab->n_param = 0; | |||
72 | tab->n_div = 0; | |||
73 | tab->n_dead = 0; | |||
74 | tab->n_redundant = 0; | |||
75 | tab->strict_redundant = 0; | |||
76 | tab->need_undo = 0; | |||
77 | tab->rational = 0; | |||
78 | tab->empty = 0; | |||
79 | tab->in_undo = 0; | |||
80 | tab->M = M; | |||
81 | tab->cone = 0; | |||
82 | tab->bottom.type = isl_tab_undo_bottom; | |||
83 | tab->bottom.next = NULL((void*)0); | |||
84 | tab->top = &tab->bottom; | |||
85 | ||||
86 | tab->n_zero = 0; | |||
87 | tab->n_unbounded = 0; | |||
88 | tab->basis = NULL((void*)0); | |||
89 | ||||
90 | return tab; | |||
91 | error: | |||
92 | isl_tab_free(tab); | |||
93 | return NULL((void*)0); | |||
94 | } | |||
95 | ||||
96 | isl_ctx *isl_tab_get_ctx(struct isl_tab *tab) | |||
97 | { | |||
98 | return tab ? isl_mat_get_ctx(tab->mat) : NULL((void*)0); | |||
99 | } | |||
100 | ||||
101 | int isl_tab_extend_cons(struct isl_tab *tab, unsigned n_new) | |||
102 | { | |||
103 | unsigned off; | |||
104 | ||||
105 | if (!tab) | |||
106 | return -1; | |||
107 | ||||
108 | off = 2 + tab->M; | |||
109 | ||||
110 | if (tab->max_con < tab->n_con + n_new) { | |||
111 | struct isl_tab_var *con; | |||
112 | ||||
113 | con = isl_realloc_array(tab->mat->ctx, tab->con,((struct isl_tab_var *)isl_realloc_or_die(tab->mat->ctx , tab->con, (tab->max_con + n_new)*sizeof(struct isl_tab_var ))) | |||
114 | struct isl_tab_var, tab->max_con + n_new)((struct isl_tab_var *)isl_realloc_or_die(tab->mat->ctx , tab->con, (tab->max_con + n_new)*sizeof(struct isl_tab_var ))); | |||
115 | if (!con) | |||
116 | return -1; | |||
117 | tab->con = con; | |||
118 | tab->max_con += n_new; | |||
119 | } | |||
120 | if (tab->mat->n_row < tab->n_row + n_new) { | |||
121 | int *row_var; | |||
122 | ||||
123 | tab->mat = isl_mat_extend(tab->mat, | |||
124 | tab->n_row + n_new, off + tab->n_col); | |||
125 | if (!tab->mat) | |||
126 | return -1; | |||
127 | row_var = isl_realloc_array(tab->mat->ctx, tab->row_var,((int *)isl_realloc_or_die(tab->mat->ctx, tab->row_var , (tab->mat->n_row)*sizeof(int))) | |||
128 | int, tab->mat->n_row)((int *)isl_realloc_or_die(tab->mat->ctx, tab->row_var , (tab->mat->n_row)*sizeof(int))); | |||
129 | if (!row_var) | |||
130 | return -1; | |||
131 | tab->row_var = row_var; | |||
132 | if (tab->row_sign) { | |||
133 | enum isl_tab_row_sign *s; | |||
134 | s = isl_realloc_array(tab->mat->ctx, tab->row_sign,((enum isl_tab_row_sign *)isl_realloc_or_die(tab->mat-> ctx, tab->row_sign, (tab->mat->n_row)*sizeof(enum isl_tab_row_sign ))) | |||
135 | enum isl_tab_row_sign, tab->mat->n_row)((enum isl_tab_row_sign *)isl_realloc_or_die(tab->mat-> ctx, tab->row_sign, (tab->mat->n_row)*sizeof(enum isl_tab_row_sign ))); | |||
136 | if (!s) | |||
137 | return -1; | |||
138 | tab->row_sign = s; | |||
139 | } | |||
140 | } | |||
141 | return 0; | |||
142 | } | |||
143 | ||||
144 | /* Make room for at least n_new extra variables. | |||
145 | * Return -1 if anything went wrong. | |||
146 | */ | |||
147 | int isl_tab_extend_vars(struct isl_tab *tab, unsigned n_new) | |||
148 | { | |||
149 | struct isl_tab_var *var; | |||
150 | unsigned off = 2 + tab->M; | |||
151 | ||||
152 | if (tab->max_var < tab->n_var + n_new) { | |||
153 | var = isl_realloc_array(tab->mat->ctx, tab->var,((struct isl_tab_var *)isl_realloc_or_die(tab->mat->ctx , tab->var, (tab->n_var + n_new)*sizeof(struct isl_tab_var ))) | |||
154 | struct isl_tab_var, tab->n_var + n_new)((struct isl_tab_var *)isl_realloc_or_die(tab->mat->ctx , tab->var, (tab->n_var + n_new)*sizeof(struct isl_tab_var ))); | |||
155 | if (!var) | |||
156 | return -1; | |||
157 | tab->var = var; | |||
158 | tab->max_var = tab->n_var + n_new; | |||
159 | } | |||
160 | ||||
161 | if (tab->mat->n_col < off + tab->n_col + n_new) { | |||
162 | int *p; | |||
163 | ||||
164 | tab->mat = isl_mat_extend(tab->mat, | |||
165 | tab->mat->n_row, off + tab->n_col + n_new); | |||
166 | if (!tab->mat) | |||
167 | return -1; | |||
168 | p = isl_realloc_array(tab->mat->ctx, tab->col_var,((int *)isl_realloc_or_die(tab->mat->ctx, tab->col_var , (tab->n_col + n_new)*sizeof(int))) | |||
169 | int, tab->n_col + n_new)((int *)isl_realloc_or_die(tab->mat->ctx, tab->col_var , (tab->n_col + n_new)*sizeof(int))); | |||
170 | if (!p) | |||
171 | return -1; | |||
172 | tab->col_var = p; | |||
173 | } | |||
174 | ||||
175 | return 0; | |||
176 | } | |||
177 | ||||
178 | static void free_undo_record(struct isl_tab_undo *undo) | |||
179 | { | |||
180 | switch (undo->type) { | |||
181 | case isl_tab_undo_saved_basis: | |||
182 | free(undo->u.col_var); | |||
183 | break; | |||
184 | default:; | |||
185 | } | |||
186 | free(undo); | |||
187 | } | |||
188 | ||||
189 | static void free_undo(struct isl_tab *tab) | |||
190 | { | |||
191 | struct isl_tab_undo *undo, *next; | |||
192 | ||||
193 | for (undo = tab->top; undo && undo != &tab->bottom; undo = next) { | |||
194 | next = undo->next; | |||
195 | free_undo_record(undo); | |||
196 | } | |||
197 | tab->top = undo; | |||
198 | } | |||
199 | ||||
200 | void isl_tab_free(struct isl_tab *tab) | |||
201 | { | |||
202 | if (!tab) | |||
203 | return; | |||
204 | free_undo(tab); | |||
205 | isl_mat_free(tab->mat); | |||
206 | isl_vec_free(tab->dual); | |||
207 | isl_basic_map_free(tab->bmap); | |||
208 | free(tab->var); | |||
209 | free(tab->con); | |||
210 | free(tab->row_var); | |||
211 | free(tab->col_var); | |||
212 | free(tab->row_sign); | |||
213 | isl_mat_free(tab->samples); | |||
214 | free(tab->sample_index); | |||
215 | isl_mat_free(tab->basis); | |||
216 | free(tab); | |||
217 | } | |||
218 | ||||
219 | struct isl_tab *isl_tab_dup(struct isl_tab *tab) | |||
220 | { | |||
221 | int i; | |||
222 | struct isl_tab *dup; | |||
223 | unsigned off; | |||
224 | ||||
225 | if (!tab) | |||
226 | return NULL((void*)0); | |||
227 | ||||
228 | off = 2 + tab->M; | |||
229 | dup = isl_calloc_type(tab->mat->ctx, struct isl_tab)((struct isl_tab *)isl_calloc_or_die(tab->mat->ctx, 1, sizeof (struct isl_tab))); | |||
230 | if (!dup) | |||
231 | return NULL((void*)0); | |||
232 | dup->mat = isl_mat_dup(tab->mat); | |||
233 | if (!dup->mat) | |||
234 | goto error; | |||
235 | dup->var = isl_alloc_array(tab->mat->ctx, struct isl_tab_var, tab->max_var)((struct isl_tab_var *)isl_malloc_or_die(tab->mat->ctx, (tab->max_var)*sizeof(struct isl_tab_var))); | |||
236 | if (tab->max_var && !dup->var) | |||
237 | goto error; | |||
238 | for (i = 0; i < tab->n_var; ++i) | |||
239 | dup->var[i] = tab->var[i]; | |||
240 | dup->con = isl_alloc_array(tab->mat->ctx, struct isl_tab_var, tab->max_con)((struct isl_tab_var *)isl_malloc_or_die(tab->mat->ctx, (tab->max_con)*sizeof(struct isl_tab_var))); | |||
241 | if (tab->max_con && !dup->con) | |||
242 | goto error; | |||
243 | for (i = 0; i < tab->n_con; ++i) | |||
244 | dup->con[i] = tab->con[i]; | |||
245 | dup->col_var = isl_alloc_array(tab->mat->ctx, int, tab->mat->n_col - off)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->mat-> n_col - off)*sizeof(int))); | |||
246 | if ((tab->mat->n_col - off) && !dup->col_var) | |||
247 | goto error; | |||
248 | for (i = 0; i < tab->n_col; ++i) | |||
249 | dup->col_var[i] = tab->col_var[i]; | |||
250 | dup->row_var = isl_alloc_array(tab->mat->ctx, int, tab->mat->n_row)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->mat-> n_row)*sizeof(int))); | |||
251 | if (tab->mat->n_row && !dup->row_var) | |||
252 | goto error; | |||
253 | for (i = 0; i < tab->n_row; ++i) | |||
254 | dup->row_var[i] = tab->row_var[i]; | |||
255 | if (tab->row_sign) { | |||
256 | dup->row_sign = isl_alloc_array(tab->mat->ctx, enum isl_tab_row_sign,((enum isl_tab_row_sign *)isl_malloc_or_die(tab->mat->ctx , (tab->mat->n_row)*sizeof(enum isl_tab_row_sign))) | |||
257 | tab->mat->n_row)((enum isl_tab_row_sign *)isl_malloc_or_die(tab->mat->ctx , (tab->mat->n_row)*sizeof(enum isl_tab_row_sign))); | |||
258 | if (tab->mat->n_row && !dup->row_sign) | |||
259 | goto error; | |||
260 | for (i = 0; i < tab->n_row; ++i) | |||
261 | dup->row_sign[i] = tab->row_sign[i]; | |||
262 | } | |||
263 | if (tab->samples) { | |||
264 | dup->samples = isl_mat_dup(tab->samples); | |||
265 | if (!dup->samples) | |||
266 | goto error; | |||
267 | dup->sample_index = isl_alloc_array(tab->mat->ctx, int,((int *)isl_malloc_or_die(tab->mat->ctx, (tab->samples ->n_row)*sizeof(int))) | |||
268 | tab->samples->n_row)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->samples ->n_row)*sizeof(int))); | |||
269 | if (tab->samples->n_row && !dup->sample_index) | |||
270 | goto error; | |||
271 | dup->n_sample = tab->n_sample; | |||
272 | dup->n_outside = tab->n_outside; | |||
273 | } | |||
274 | dup->n_row = tab->n_row; | |||
275 | dup->n_con = tab->n_con; | |||
276 | dup->n_eq = tab->n_eq; | |||
277 | dup->max_con = tab->max_con; | |||
278 | dup->n_col = tab->n_col; | |||
279 | dup->n_var = tab->n_var; | |||
280 | dup->max_var = tab->max_var; | |||
281 | dup->n_param = tab->n_param; | |||
282 | dup->n_div = tab->n_div; | |||
283 | dup->n_dead = tab->n_dead; | |||
284 | dup->n_redundant = tab->n_redundant; | |||
285 | dup->rational = tab->rational; | |||
286 | dup->empty = tab->empty; | |||
287 | dup->strict_redundant = 0; | |||
288 | dup->need_undo = 0; | |||
289 | dup->in_undo = 0; | |||
290 | dup->M = tab->M; | |||
291 | tab->cone = tab->cone; | |||
292 | dup->bottom.type = isl_tab_undo_bottom; | |||
293 | dup->bottom.next = NULL((void*)0); | |||
294 | dup->top = &dup->bottom; | |||
295 | ||||
296 | dup->n_zero = tab->n_zero; | |||
297 | dup->n_unbounded = tab->n_unbounded; | |||
298 | dup->basis = isl_mat_dup(tab->basis); | |||
299 | ||||
300 | return dup; | |||
301 | error: | |||
302 | isl_tab_free(dup); | |||
303 | return NULL((void*)0); | |||
304 | } | |||
305 | ||||
306 | /* Construct the coefficient matrix of the product tableau | |||
307 | * of two tableaus. | |||
308 | * mat{1,2} is the coefficient matrix of tableau {1,2} | |||
309 | * row{1,2} is the number of rows in tableau {1,2} | |||
310 | * col{1,2} is the number of columns in tableau {1,2} | |||
311 | * off is the offset to the coefficient column (skipping the | |||
312 | * denominator, the constant term and the big parameter if any) | |||
313 | * r{1,2} is the number of redundant rows in tableau {1,2} | |||
314 | * d{1,2} is the number of dead columns in tableau {1,2} | |||
315 | * | |||
316 | * The order of the rows and columns in the result is as explained | |||
317 | * in isl_tab_product. | |||
318 | */ | |||
319 | static struct isl_mat *tab_mat_product(struct isl_mat *mat1, | |||
320 | struct isl_mat *mat2, unsigned row1, unsigned row2, | |||
321 | unsigned col1, unsigned col2, | |||
322 | unsigned off, unsigned r1, unsigned r2, unsigned d1, unsigned d2) | |||
323 | { | |||
324 | int i; | |||
325 | struct isl_mat *prod; | |||
326 | unsigned n; | |||
327 | ||||
328 | prod = isl_mat_alloc(mat1->ctx, mat1->n_row + mat2->n_row, | |||
329 | off + col1 + col2); | |||
330 | if (!prod) | |||
331 | return NULL((void*)0); | |||
332 | ||||
333 | n = 0; | |||
334 | for (i = 0; i < r1; ++i) { | |||
335 | isl_seq_cpy(prod->row[n + i], mat1->row[i], off + d1); | |||
336 | isl_seq_clr(prod->row[n + i] + off + d1, d2); | |||
337 | isl_seq_cpy(prod->row[n + i] + off + d1 + d2, | |||
338 | mat1->row[i] + off + d1, col1 - d1); | |||
339 | isl_seq_clr(prod->row[n + i] + off + col1 + d1, col2 - d2); | |||
340 | } | |||
341 | ||||
342 | n += r1; | |||
343 | for (i = 0; i < r2; ++i) { | |||
344 | isl_seq_cpy(prod->row[n + i], mat2->row[i], off); | |||
345 | isl_seq_clr(prod->row[n + i] + off, d1); | |||
346 | isl_seq_cpy(prod->row[n + i] + off + d1, | |||
347 | mat2->row[i] + off, d2); | |||
348 | isl_seq_clr(prod->row[n + i] + off + d1 + d2, col1 - d1); | |||
349 | isl_seq_cpy(prod->row[n + i] + off + col1 + d1, | |||
350 | mat2->row[i] + off + d2, col2 - d2); | |||
351 | } | |||
352 | ||||
353 | n += r2; | |||
354 | for (i = 0; i < row1 - r1; ++i) { | |||
355 | isl_seq_cpy(prod->row[n + i], mat1->row[r1 + i], off + d1); | |||
356 | isl_seq_clr(prod->row[n + i] + off + d1, d2); | |||
357 | isl_seq_cpy(prod->row[n + i] + off + d1 + d2, | |||
358 | mat1->row[r1 + i] + off + d1, col1 - d1); | |||
359 | isl_seq_clr(prod->row[n + i] + off + col1 + d1, col2 - d2); | |||
360 | } | |||
361 | ||||
362 | n += row1 - r1; | |||
363 | for (i = 0; i < row2 - r2; ++i) { | |||
364 | isl_seq_cpy(prod->row[n + i], mat2->row[r2 + i], off); | |||
365 | isl_seq_clr(prod->row[n + i] + off, d1); | |||
366 | isl_seq_cpy(prod->row[n + i] + off + d1, | |||
367 | mat2->row[r2 + i] + off, d2); | |||
368 | isl_seq_clr(prod->row[n + i] + off + d1 + d2, col1 - d1); | |||
369 | isl_seq_cpy(prod->row[n + i] + off + col1 + d1, | |||
370 | mat2->row[r2 + i] + off + d2, col2 - d2); | |||
371 | } | |||
372 | ||||
373 | return prod; | |||
374 | } | |||
375 | ||||
376 | /* Update the row or column index of a variable that corresponds | |||
377 | * to a variable in the first input tableau. | |||
378 | */ | |||
379 | static void update_index1(struct isl_tab_var *var, | |||
380 | unsigned r1, unsigned r2, unsigned d1, unsigned d2) | |||
381 | { | |||
382 | if (var->index == -1) | |||
383 | return; | |||
384 | if (var->is_row && var->index >= r1) | |||
385 | var->index += r2; | |||
386 | if (!var->is_row && var->index >= d1) | |||
387 | var->index += d2; | |||
388 | } | |||
389 | ||||
390 | /* Update the row or column index of a variable that corresponds | |||
391 | * to a variable in the second input tableau. | |||
392 | */ | |||
393 | static void update_index2(struct isl_tab_var *var, | |||
394 | unsigned row1, unsigned col1, | |||
395 | unsigned r1, unsigned r2, unsigned d1, unsigned d2) | |||
396 | { | |||
397 | if (var->index == -1) | |||
398 | return; | |||
399 | if (var->is_row) { | |||
400 | if (var->index < r2) | |||
401 | var->index += r1; | |||
402 | else | |||
403 | var->index += row1; | |||
404 | } else { | |||
405 | if (var->index < d2) | |||
406 | var->index += d1; | |||
407 | else | |||
408 | var->index += col1; | |||
409 | } | |||
410 | } | |||
411 | ||||
412 | /* Create a tableau that represents the Cartesian product of the sets | |||
413 | * represented by tableaus tab1 and tab2. | |||
414 | * The order of the rows in the product is | |||
415 | * - redundant rows of tab1 | |||
416 | * - redundant rows of tab2 | |||
417 | * - non-redundant rows of tab1 | |||
418 | * - non-redundant rows of tab2 | |||
419 | * The order of the columns is | |||
420 | * - denominator | |||
421 | * - constant term | |||
422 | * - coefficient of big parameter, if any | |||
423 | * - dead columns of tab1 | |||
424 | * - dead columns of tab2 | |||
425 | * - live columns of tab1 | |||
426 | * - live columns of tab2 | |||
427 | * The order of the variables and the constraints is a concatenation | |||
428 | * of order in the two input tableaus. | |||
429 | */ | |||
430 | struct isl_tab *isl_tab_product(struct isl_tab *tab1, struct isl_tab *tab2) | |||
431 | { | |||
432 | int i; | |||
433 | struct isl_tab *prod; | |||
434 | unsigned off; | |||
435 | unsigned r1, r2, d1, d2; | |||
436 | ||||
437 | if (!tab1 || !tab2) | |||
438 | return NULL((void*)0); | |||
439 | ||||
440 | isl_assert(tab1->mat->ctx, tab1->M == tab2->M, return NULL)do { if (tab1->M == tab2->M) break; do { isl_handle_error (tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->M == tab2->M" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 440); return ((void*)0); } while (0); } while (0); | |||
441 | isl_assert(tab1->mat->ctx, tab1->rational == tab2->rational, return NULL)do { if (tab1->rational == tab2->rational) break; do { isl_handle_error (tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->rational == tab2->rational" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 441); return ((void*)0); } while (0); } while (0); | |||
442 | isl_assert(tab1->mat->ctx, tab1->cone == tab2->cone, return NULL)do { if (tab1->cone == tab2->cone) break; do { isl_handle_error (tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->cone == tab2->cone" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 442); return ((void*)0); } while (0); } while (0); | |||
443 | isl_assert(tab1->mat->ctx, !tab1->row_sign, return NULL)do { if (!tab1->row_sign) break; do { isl_handle_error(tab1 ->mat->ctx, isl_error_unknown, "Assertion \"" "!tab1->row_sign" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 443); return ((void*)0); } while (0); } while (0); | |||
444 | isl_assert(tab1->mat->ctx, !tab2->row_sign, return NULL)do { if (!tab2->row_sign) break; do { isl_handle_error(tab1 ->mat->ctx, isl_error_unknown, "Assertion \"" "!tab2->row_sign" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 444); return ((void*)0); } while (0); } while (0); | |||
445 | isl_assert(tab1->mat->ctx, tab1->n_param == 0, return NULL)do { if (tab1->n_param == 0) break; do { isl_handle_error( tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->n_param == 0" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 445); return ((void*)0); } while (0); } while (0); | |||
446 | isl_assert(tab1->mat->ctx, tab2->n_param == 0, return NULL)do { if (tab2->n_param == 0) break; do { isl_handle_error( tab1->mat->ctx, isl_error_unknown, "Assertion \"" "tab2->n_param == 0" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 446); return ((void*)0); } while (0); } while (0); | |||
447 | isl_assert(tab1->mat->ctx, tab1->n_div == 0, return NULL)do { if (tab1->n_div == 0) break; do { isl_handle_error(tab1 ->mat->ctx, isl_error_unknown, "Assertion \"" "tab1->n_div == 0" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 447); return ((void*)0); } while (0); } while (0); | |||
448 | isl_assert(tab1->mat->ctx, tab2->n_div == 0, return NULL)do { if (tab2->n_div == 0) break; do { isl_handle_error(tab1 ->mat->ctx, isl_error_unknown, "Assertion \"" "tab2->n_div == 0" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 448); return ((void*)0); } while (0); } while (0); | |||
449 | ||||
450 | off = 2 + tab1->M; | |||
451 | r1 = tab1->n_redundant; | |||
452 | r2 = tab2->n_redundant; | |||
453 | d1 = tab1->n_dead; | |||
454 | d2 = tab2->n_dead; | |||
455 | prod = isl_calloc_type(tab1->mat->ctx, struct isl_tab)((struct isl_tab *)isl_calloc_or_die(tab1->mat->ctx, 1, sizeof(struct isl_tab))); | |||
456 | if (!prod) | |||
457 | return NULL((void*)0); | |||
458 | prod->mat = tab_mat_product(tab1->mat, tab2->mat, | |||
459 | tab1->n_row, tab2->n_row, | |||
460 | tab1->n_col, tab2->n_col, off, r1, r2, d1, d2); | |||
461 | if (!prod->mat) | |||
462 | goto error; | |||
463 | prod->var = isl_alloc_array(tab1->mat->ctx, struct isl_tab_var,((struct isl_tab_var *)isl_malloc_or_die(tab1->mat->ctx , (tab1->max_var + tab2->max_var)*sizeof(struct isl_tab_var ))) | |||
464 | tab1->max_var + tab2->max_var)((struct isl_tab_var *)isl_malloc_or_die(tab1->mat->ctx , (tab1->max_var + tab2->max_var)*sizeof(struct isl_tab_var ))); | |||
465 | if ((tab1->max_var + tab2->max_var) && !prod->var) | |||
466 | goto error; | |||
467 | for (i = 0; i < tab1->n_var; ++i) { | |||
468 | prod->var[i] = tab1->var[i]; | |||
469 | update_index1(&prod->var[i], r1, r2, d1, d2); | |||
470 | } | |||
471 | for (i = 0; i < tab2->n_var; ++i) { | |||
472 | prod->var[tab1->n_var + i] = tab2->var[i]; | |||
473 | update_index2(&prod->var[tab1->n_var + i], | |||
474 | tab1->n_row, tab1->n_col, | |||
475 | r1, r2, d1, d2); | |||
476 | } | |||
477 | prod->con = isl_alloc_array(tab1->mat->ctx, struct isl_tab_var,((struct isl_tab_var *)isl_malloc_or_die(tab1->mat->ctx , (tab1->max_con + tab2->max_con)*sizeof(struct isl_tab_var ))) | |||
478 | tab1->max_con + tab2->max_con)((struct isl_tab_var *)isl_malloc_or_die(tab1->mat->ctx , (tab1->max_con + tab2->max_con)*sizeof(struct isl_tab_var ))); | |||
479 | if ((tab1->max_con + tab2->max_con) && !prod->con) | |||
480 | goto error; | |||
481 | for (i = 0; i < tab1->n_con; ++i) { | |||
482 | prod->con[i] = tab1->con[i]; | |||
483 | update_index1(&prod->con[i], r1, r2, d1, d2); | |||
484 | } | |||
485 | for (i = 0; i < tab2->n_con; ++i) { | |||
486 | prod->con[tab1->n_con + i] = tab2->con[i]; | |||
487 | update_index2(&prod->con[tab1->n_con + i], | |||
488 | tab1->n_row, tab1->n_col, | |||
489 | r1, r2, d1, d2); | |||
490 | } | |||
491 | prod->col_var = isl_alloc_array(tab1->mat->ctx, int,((int *)isl_malloc_or_die(tab1->mat->ctx, (tab1->n_col + tab2->n_col)*sizeof(int))) | |||
492 | tab1->n_col + tab2->n_col)((int *)isl_malloc_or_die(tab1->mat->ctx, (tab1->n_col + tab2->n_col)*sizeof(int))); | |||
493 | if ((tab1->n_col + tab2->n_col) && !prod->col_var) | |||
494 | goto error; | |||
495 | for (i = 0; i < tab1->n_col; ++i) { | |||
496 | int pos = i < d1 ? i : i + d2; | |||
497 | prod->col_var[pos] = tab1->col_var[i]; | |||
498 | } | |||
499 | for (i = 0; i < tab2->n_col; ++i) { | |||
500 | int pos = i < d2 ? d1 + i : tab1->n_col + i; | |||
501 | int t = tab2->col_var[i]; | |||
502 | if (t >= 0) | |||
503 | t += tab1->n_var; | |||
504 | else | |||
505 | t -= tab1->n_con; | |||
506 | prod->col_var[pos] = t; | |||
507 | } | |||
508 | prod->row_var = isl_alloc_array(tab1->mat->ctx, int,((int *)isl_malloc_or_die(tab1->mat->ctx, (tab1->mat ->n_row + tab2->mat->n_row)*sizeof(int))) | |||
509 | tab1->mat->n_row + tab2->mat->n_row)((int *)isl_malloc_or_die(tab1->mat->ctx, (tab1->mat ->n_row + tab2->mat->n_row)*sizeof(int))); | |||
510 | if ((tab1->mat->n_row + tab2->mat->n_row) && !prod->row_var) | |||
511 | goto error; | |||
512 | for (i = 0; i < tab1->n_row; ++i) { | |||
513 | int pos = i < r1 ? i : i + r2; | |||
514 | prod->row_var[pos] = tab1->row_var[i]; | |||
515 | } | |||
516 | for (i = 0; i < tab2->n_row; ++i) { | |||
517 | int pos = i < r2 ? r1 + i : tab1->n_row + i; | |||
518 | int t = tab2->row_var[i]; | |||
519 | if (t >= 0) | |||
520 | t += tab1->n_var; | |||
521 | else | |||
522 | t -= tab1->n_con; | |||
523 | prod->row_var[pos] = t; | |||
524 | } | |||
525 | prod->samples = NULL((void*)0); | |||
526 | prod->sample_index = NULL((void*)0); | |||
527 | prod->n_row = tab1->n_row + tab2->n_row; | |||
528 | prod->n_con = tab1->n_con + tab2->n_con; | |||
529 | prod->n_eq = 0; | |||
530 | prod->max_con = tab1->max_con + tab2->max_con; | |||
531 | prod->n_col = tab1->n_col + tab2->n_col; | |||
532 | prod->n_var = tab1->n_var + tab2->n_var; | |||
533 | prod->max_var = tab1->max_var + tab2->max_var; | |||
534 | prod->n_param = 0; | |||
535 | prod->n_div = 0; | |||
536 | prod->n_dead = tab1->n_dead + tab2->n_dead; | |||
537 | prod->n_redundant = tab1->n_redundant + tab2->n_redundant; | |||
538 | prod->rational = tab1->rational; | |||
539 | prod->empty = tab1->empty || tab2->empty; | |||
540 | prod->strict_redundant = tab1->strict_redundant || tab2->strict_redundant; | |||
541 | prod->need_undo = 0; | |||
542 | prod->in_undo = 0; | |||
543 | prod->M = tab1->M; | |||
544 | prod->cone = tab1->cone; | |||
545 | prod->bottom.type = isl_tab_undo_bottom; | |||
546 | prod->bottom.next = NULL((void*)0); | |||
547 | prod->top = &prod->bottom; | |||
548 | ||||
549 | prod->n_zero = 0; | |||
550 | prod->n_unbounded = 0; | |||
551 | prod->basis = NULL((void*)0); | |||
552 | ||||
553 | return prod; | |||
554 | error: | |||
555 | isl_tab_free(prod); | |||
556 | return NULL((void*)0); | |||
557 | } | |||
558 | ||||
559 | static struct isl_tab_var *var_from_index(struct isl_tab *tab, int i) | |||
560 | { | |||
561 | if (i >= 0) | |||
562 | return &tab->var[i]; | |||
563 | else | |||
564 | return &tab->con[~i]; | |||
565 | } | |||
566 | ||||
567 | struct isl_tab_var *isl_tab_var_from_row(struct isl_tab *tab, int i) | |||
568 | { | |||
569 | return var_from_index(tab, tab->row_var[i]); | |||
570 | } | |||
571 | ||||
572 | static struct isl_tab_var *var_from_col(struct isl_tab *tab, int i) | |||
573 | { | |||
574 | return var_from_index(tab, tab->col_var[i]); | |||
575 | } | |||
576 | ||||
577 | /* Check if there are any upper bounds on column variable "var", | |||
578 | * i.e., non-negative rows where var appears with a negative coefficient. | |||
579 | * Return 1 if there are no such bounds. | |||
580 | */ | |||
581 | static int max_is_manifestly_unbounded(struct isl_tab *tab, | |||
582 | struct isl_tab_var *var) | |||
583 | { | |||
584 | int i; | |||
585 | unsigned off = 2 + tab->M; | |||
586 | ||||
587 | if (var->is_row) | |||
588 | return 0; | |||
589 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
590 | if (!isl_int_is_neg(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index ])) < 0)) | |||
591 | continue; | |||
592 | if (isl_tab_var_from_row(tab, i)->is_nonneg) | |||
593 | return 0; | |||
594 | } | |||
595 | return 1; | |||
596 | } | |||
597 | ||||
598 | /* Check if there are any lower bounds on column variable "var", | |||
599 | * i.e., non-negative rows where var appears with a positive coefficient. | |||
600 | * Return 1 if there are no such bounds. | |||
601 | */ | |||
602 | static int min_is_manifestly_unbounded(struct isl_tab *tab, | |||
603 | struct isl_tab_var *var) | |||
604 | { | |||
605 | int i; | |||
606 | unsigned off = 2 + tab->M; | |||
607 | ||||
608 | if (var->is_row) | |||
609 | return 0; | |||
610 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
611 | if (!isl_int_is_pos(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index ])) > 0)) | |||
612 | continue; | |||
613 | if (isl_tab_var_from_row(tab, i)->is_nonneg) | |||
614 | return 0; | |||
615 | } | |||
616 | return 1; | |||
617 | } | |||
618 | ||||
619 | static int row_cmp(struct isl_tab *tab, int r1, int r2, int c, isl_int *t) | |||
620 | { | |||
621 | unsigned off = 2 + tab->M; | |||
622 | ||||
623 | if (tab->M) { | |||
624 | int s; | |||
625 | isl_int_mul(*t, tab->mat->row[r1][2], tab->mat->row[r2][off+c])isl_sioimath_mul((*t), *(tab->mat->row[r1][2]), *(tab-> mat->row[r2][off+c])); | |||
626 | isl_int_submul(*t, tab->mat->row[r2][2], tab->mat->row[r1][off+c])isl_sioimath_submul((*t), *(tab->mat->row[r2][2]), *(tab ->mat->row[r1][off+c])); | |||
627 | s = isl_int_sgn(*t)isl_sioimath_sgn(*(*t)); | |||
628 | if (s) | |||
629 | return s; | |||
630 | } | |||
631 | isl_int_mul(*t, tab->mat->row[r1][1], tab->mat->row[r2][off + c])isl_sioimath_mul((*t), *(tab->mat->row[r1][1]), *(tab-> mat->row[r2][off + c])); | |||
632 | isl_int_submul(*t, tab->mat->row[r2][1], tab->mat->row[r1][off + c])isl_sioimath_submul((*t), *(tab->mat->row[r2][1]), *(tab ->mat->row[r1][off + c])); | |||
633 | return isl_int_sgn(*t)isl_sioimath_sgn(*(*t)); | |||
634 | } | |||
635 | ||||
636 | /* Given the index of a column "c", return the index of a row | |||
637 | * that can be used to pivot the column in, with either an increase | |||
638 | * (sgn > 0) or a decrease (sgn < 0) of the corresponding variable. | |||
639 | * If "var" is not NULL, then the row returned will be different from | |||
640 | * the one associated with "var". | |||
641 | * | |||
642 | * Each row in the tableau is of the form | |||
643 | * | |||
644 | * x_r = a_r0 + \sum_i a_ri x_i | |||
645 | * | |||
646 | * Only rows with x_r >= 0 and with the sign of a_ri opposite to "sgn" | |||
647 | * impose any limit on the increase or decrease in the value of x_c | |||
648 | * and this bound is equal to a_r0 / |a_rc|. We are therefore looking | |||
649 | * for the row with the smallest (most stringent) such bound. | |||
650 | * Note that the common denominator of each row drops out of the fraction. | |||
651 | * To check if row j has a smaller bound than row r, i.e., | |||
652 | * a_j0 / |a_jc| < a_r0 / |a_rc| or a_j0 |a_rc| < a_r0 |a_jc|, | |||
653 | * we check if -sign(a_jc) (a_j0 a_rc - a_r0 a_jc) < 0, | |||
654 | * where -sign(a_jc) is equal to "sgn". | |||
655 | */ | |||
656 | static int pivot_row(struct isl_tab *tab, | |||
657 | struct isl_tab_var *var, int sgn, int c) | |||
658 | { | |||
659 | int j, r, tsgn; | |||
660 | isl_int t; | |||
661 | unsigned off = 2 + tab->M; | |||
662 | ||||
663 | isl_int_init(t)isl_sioimath_init((t)); | |||
664 | r = -1; | |||
665 | for (j = tab->n_redundant; j < tab->n_row; ++j) { | |||
666 | if (var && j == var->index) | |||
667 | continue; | |||
668 | if (!isl_tab_var_from_row(tab, j)->is_nonneg) | |||
669 | continue; | |||
670 | if (sgn * isl_int_sgn(tab->mat->row[j][off + c])isl_sioimath_sgn(*(tab->mat->row[j][off + c])) >= 0) | |||
671 | continue; | |||
672 | if (r < 0) { | |||
673 | r = j; | |||
674 | continue; | |||
675 | } | |||
676 | tsgn = sgn * row_cmp(tab, r, j, c, &t); | |||
677 | if (tsgn < 0 || (tsgn == 0 && | |||
678 | tab->row_var[j] < tab->row_var[r])) | |||
679 | r = j; | |||
680 | } | |||
681 | isl_int_clear(t)isl_sioimath_clear((t)); | |||
682 | return r; | |||
683 | } | |||
684 | ||||
685 | /* Find a pivot (row and col) that will increase (sgn > 0) or decrease | |||
686 | * (sgn < 0) the value of row variable var. | |||
687 | * If not NULL, then skip_var is a row variable that should be ignored | |||
688 | * while looking for a pivot row. It is usually equal to var. | |||
689 | * | |||
690 | * As the given row in the tableau is of the form | |||
691 | * | |||
692 | * x_r = a_r0 + \sum_i a_ri x_i | |||
693 | * | |||
694 | * we need to find a column such that the sign of a_ri is equal to "sgn" | |||
695 | * (such that an increase in x_i will have the desired effect) or a | |||
696 | * column with a variable that may attain negative values. | |||
697 | * If a_ri is positive, then we need to move x_i in the same direction | |||
698 | * to obtain the desired effect. Otherwise, x_i has to move in the | |||
699 | * opposite direction. | |||
700 | */ | |||
701 | static void find_pivot(struct isl_tab *tab, | |||
702 | struct isl_tab_var *var, struct isl_tab_var *skip_var, | |||
703 | int sgn, int *row, int *col) | |||
704 | { | |||
705 | int j, r, c; | |||
706 | isl_int *tr; | |||
707 | ||||
708 | *row = *col = -1; | |||
709 | ||||
710 | isl_assert(tab->mat->ctx, var->is_row, return)do { if (var->is_row) break; do { isl_handle_error(tab-> mat->ctx, isl_error_unknown, "Assertion \"" "var->is_row" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 710); return; } while (0); } while (0); | |||
711 | tr = tab->mat->row[var->index] + 2 + tab->M; | |||
712 | ||||
713 | c = -1; | |||
714 | for (j = tab->n_dead; j < tab->n_col; ++j) { | |||
715 | if (isl_int_is_zero(tr[j])(isl_sioimath_sgn(*(tr[j])) == 0)) | |||
716 | continue; | |||
717 | if (isl_int_sgn(tr[j])isl_sioimath_sgn(*(tr[j])) != sgn && | |||
718 | var_from_col(tab, j)->is_nonneg) | |||
719 | continue; | |||
720 | if (c < 0 || tab->col_var[j] < tab->col_var[c]) | |||
721 | c = j; | |||
722 | } | |||
723 | if (c < 0) | |||
724 | return; | |||
725 | ||||
726 | sgn *= isl_int_sgn(tr[c])isl_sioimath_sgn(*(tr[c])); | |||
727 | r = pivot_row(tab, skip_var, sgn, c); | |||
728 | *row = r < 0 ? var->index : r; | |||
729 | *col = c; | |||
730 | } | |||
731 | ||||
732 | /* Return 1 if row "row" represents an obviously redundant inequality. | |||
733 | * This means | |||
734 | * - it represents an inequality or a variable | |||
735 | * - that is the sum of a non-negative sample value and a positive | |||
736 | * combination of zero or more non-negative constraints. | |||
737 | */ | |||
738 | int isl_tab_row_is_redundant(struct isl_tab *tab, int row) | |||
739 | { | |||
740 | int i; | |||
741 | unsigned off = 2 + tab->M; | |||
742 | ||||
743 | if (tab->row_var[row] < 0 && !isl_tab_var_from_row(tab, row)->is_nonneg) | |||
744 | return 0; | |||
745 | ||||
746 | if (isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0)) | |||
747 | return 0; | |||
748 | if (tab->strict_redundant && isl_int_is_zero(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) == 0)) | |||
749 | return 0; | |||
750 | if (tab->M && isl_int_is_neg(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) < 0)) | |||
751 | return 0; | |||
752 | ||||
753 | for (i = tab->n_dead; i < tab->n_col; ++i) { | |||
754 | if (isl_int_is_zero(tab->mat->row[row][off + i])(isl_sioimath_sgn(*(tab->mat->row[row][off + i])) == 0)) | |||
755 | continue; | |||
756 | if (tab->col_var[i] >= 0) | |||
757 | return 0; | |||
758 | if (isl_int_is_neg(tab->mat->row[row][off + i])(isl_sioimath_sgn(*(tab->mat->row[row][off + i])) < 0 )) | |||
759 | return 0; | |||
760 | if (!var_from_col(tab, i)->is_nonneg) | |||
761 | return 0; | |||
762 | } | |||
763 | return 1; | |||
764 | } | |||
765 | ||||
766 | static void swap_rows(struct isl_tab *tab, int row1, int row2) | |||
767 | { | |||
768 | int t; | |||
769 | enum isl_tab_row_sign s; | |||
770 | ||||
771 | t = tab->row_var[row1]; | |||
772 | tab->row_var[row1] = tab->row_var[row2]; | |||
773 | tab->row_var[row2] = t; | |||
774 | isl_tab_var_from_row(tab, row1)->index = row1; | |||
775 | isl_tab_var_from_row(tab, row2)->index = row2; | |||
776 | tab->mat = isl_mat_swap_rows(tab->mat, row1, row2); | |||
777 | ||||
778 | if (!tab->row_sign) | |||
779 | return; | |||
780 | s = tab->row_sign[row1]; | |||
781 | tab->row_sign[row1] = tab->row_sign[row2]; | |||
782 | tab->row_sign[row2] = s; | |||
783 | } | |||
784 | ||||
785 | static int push_union(struct isl_tab *tab, | |||
786 | enum isl_tab_undo_type type, union isl_tab_undo_val u) WARN_UNUSED__attribute__((__warn_unused_result__)); | |||
787 | static int push_union(struct isl_tab *tab, | |||
788 | enum isl_tab_undo_type type, union isl_tab_undo_val u) | |||
789 | { | |||
790 | struct isl_tab_undo *undo; | |||
791 | ||||
792 | if (!tab) | |||
793 | return -1; | |||
794 | if (!tab->need_undo) | |||
795 | return 0; | |||
796 | ||||
797 | undo = isl_alloc_type(tab->mat->ctx, struct isl_tab_undo)((struct isl_tab_undo *)isl_malloc_or_die(tab->mat->ctx , sizeof(struct isl_tab_undo))); | |||
798 | if (!undo) | |||
799 | return -1; | |||
800 | undo->type = type; | |||
801 | undo->u = u; | |||
802 | undo->next = tab->top; | |||
803 | tab->top = undo; | |||
804 | ||||
805 | return 0; | |||
806 | } | |||
807 | ||||
808 | int isl_tab_push_var(struct isl_tab *tab, | |||
809 | enum isl_tab_undo_type type, struct isl_tab_var *var) | |||
810 | { | |||
811 | union isl_tab_undo_val u; | |||
812 | if (var->is_row) | |||
813 | u.var_index = tab->row_var[var->index]; | |||
814 | else | |||
815 | u.var_index = tab->col_var[var->index]; | |||
816 | return push_union(tab, type, u); | |||
817 | } | |||
818 | ||||
819 | int isl_tab_push(struct isl_tab *tab, enum isl_tab_undo_type type) | |||
820 | { | |||
821 | union isl_tab_undo_val u = { 0 }; | |||
822 | return push_union(tab, type, u); | |||
823 | } | |||
824 | ||||
825 | /* Push a record on the undo stack describing the current basic | |||
826 | * variables, so that the this state can be restored during rollback. | |||
827 | */ | |||
828 | int isl_tab_push_basis(struct isl_tab *tab) | |||
829 | { | |||
830 | int i; | |||
831 | union isl_tab_undo_val u; | |||
832 | ||||
833 | u.col_var = isl_alloc_array(tab->mat->ctx, int, tab->n_col)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->n_col )*sizeof(int))); | |||
834 | if (tab->n_col && !u.col_var) | |||
835 | return -1; | |||
836 | for (i = 0; i < tab->n_col; ++i) | |||
837 | u.col_var[i] = tab->col_var[i]; | |||
838 | return push_union(tab, isl_tab_undo_saved_basis, u); | |||
839 | } | |||
840 | ||||
841 | int isl_tab_push_callback(struct isl_tab *tab, struct isl_tab_callback *callback) | |||
842 | { | |||
843 | union isl_tab_undo_val u; | |||
844 | u.callback = callback; | |||
845 | return push_union(tab, isl_tab_undo_callback, u); | |||
846 | } | |||
847 | ||||
848 | struct isl_tab *isl_tab_init_samples(struct isl_tab *tab) | |||
849 | { | |||
850 | if (!tab) | |||
851 | return NULL((void*)0); | |||
852 | ||||
853 | tab->n_sample = 0; | |||
854 | tab->n_outside = 0; | |||
855 | tab->samples = isl_mat_alloc(tab->mat->ctx, 1, 1 + tab->n_var); | |||
856 | if (!tab->samples) | |||
857 | goto error; | |||
858 | tab->sample_index = isl_alloc_array(tab->mat->ctx, int, 1)((int *)isl_malloc_or_die(tab->mat->ctx, (1)*sizeof(int ))); | |||
859 | if (!tab->sample_index) | |||
860 | goto error; | |||
861 | return tab; | |||
862 | error: | |||
863 | isl_tab_free(tab); | |||
864 | return NULL((void*)0); | |||
865 | } | |||
866 | ||||
867 | int isl_tab_add_sample(struct isl_tab *tab, __isl_take isl_vec *sample) | |||
868 | { | |||
869 | if (!tab || !sample) | |||
870 | goto error; | |||
871 | ||||
872 | if (tab->n_sample + 1 > tab->samples->n_row) { | |||
873 | int *t = isl_realloc_array(tab->mat->ctx,((int *)isl_realloc_or_die(tab->mat->ctx, tab->sample_index , (tab->n_sample + 1)*sizeof(int))) | |||
874 | tab->sample_index, int, tab->n_sample + 1)((int *)isl_realloc_or_die(tab->mat->ctx, tab->sample_index , (tab->n_sample + 1)*sizeof(int))); | |||
875 | if (!t) | |||
876 | goto error; | |||
877 | tab->sample_index = t; | |||
878 | } | |||
879 | ||||
880 | tab->samples = isl_mat_extend(tab->samples, | |||
881 | tab->n_sample + 1, tab->samples->n_col); | |||
882 | if (!tab->samples) | |||
883 | goto error; | |||
884 | ||||
885 | isl_seq_cpy(tab->samples->row[tab->n_sample], sample->el, sample->size); | |||
886 | isl_vec_free(sample); | |||
887 | tab->sample_index[tab->n_sample] = tab->n_sample; | |||
888 | tab->n_sample++; | |||
889 | ||||
890 | return 0; | |||
891 | error: | |||
892 | isl_vec_free(sample); | |||
893 | return -1; | |||
894 | } | |||
895 | ||||
896 | struct isl_tab *isl_tab_drop_sample(struct isl_tab *tab, int s) | |||
897 | { | |||
898 | if (s != tab->n_outside) { | |||
899 | int t = tab->sample_index[tab->n_outside]; | |||
900 | tab->sample_index[tab->n_outside] = tab->sample_index[s]; | |||
901 | tab->sample_index[s] = t; | |||
902 | isl_mat_swap_rows(tab->samples, tab->n_outside, s); | |||
903 | } | |||
904 | tab->n_outside++; | |||
905 | if (isl_tab_push(tab, isl_tab_undo_drop_sample) < 0) { | |||
906 | isl_tab_free(tab); | |||
907 | return NULL((void*)0); | |||
908 | } | |||
909 | ||||
910 | return tab; | |||
911 | } | |||
912 | ||||
913 | /* Record the current number of samples so that we can remove newer | |||
914 | * samples during a rollback. | |||
915 | */ | |||
916 | int isl_tab_save_samples(struct isl_tab *tab) | |||
917 | { | |||
918 | union isl_tab_undo_val u; | |||
919 | ||||
920 | if (!tab) | |||
921 | return -1; | |||
922 | ||||
923 | u.n = tab->n_sample; | |||
924 | return push_union(tab, isl_tab_undo_saved_samples, u); | |||
925 | } | |||
926 | ||||
927 | /* Mark row with index "row" as being redundant. | |||
928 | * If we may need to undo the operation or if the row represents | |||
929 | * a variable of the original problem, the row is kept, | |||
930 | * but no longer considered when looking for a pivot row. | |||
931 | * Otherwise, the row is simply removed. | |||
932 | * | |||
933 | * The row may be interchanged with some other row. If it | |||
934 | * is interchanged with a later row, return 1. Otherwise return 0. | |||
935 | * If the rows are checked in order in the calling function, | |||
936 | * then a return value of 1 means that the row with the given | |||
937 | * row number may now contain a different row that hasn't been checked yet. | |||
938 | */ | |||
939 | int isl_tab_mark_redundant(struct isl_tab *tab, int row) | |||
940 | { | |||
941 | struct isl_tab_var *var = isl_tab_var_from_row(tab, row); | |||
942 | var->is_redundant = 1; | |||
943 | isl_assert(tab->mat->ctx, row >= tab->n_redundant, return -1)do { if (row >= tab->n_redundant) break; do { isl_handle_error (tab->mat->ctx, isl_error_unknown, "Assertion \"" "row >= tab->n_redundant" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 943); return -1; } while (0); } while (0); | |||
944 | if (tab->preserve || tab->need_undo || tab->row_var[row] >= 0) { | |||
945 | if (tab->row_var[row] >= 0 && !var->is_nonneg) { | |||
946 | var->is_nonneg = 1; | |||
947 | if (isl_tab_push_var(tab, isl_tab_undo_nonneg, var) < 0) | |||
948 | return -1; | |||
949 | } | |||
950 | if (row != tab->n_redundant) | |||
951 | swap_rows(tab, row, tab->n_redundant); | |||
952 | tab->n_redundant++; | |||
953 | return isl_tab_push_var(tab, isl_tab_undo_redundant, var); | |||
954 | } else { | |||
955 | if (row != tab->n_row - 1) | |||
956 | swap_rows(tab, row, tab->n_row - 1); | |||
957 | isl_tab_var_from_row(tab, tab->n_row - 1)->index = -1; | |||
958 | tab->n_row--; | |||
959 | return 1; | |||
960 | } | |||
961 | } | |||
962 | ||||
963 | /* Mark "tab" as a rational tableau. | |||
964 | * If it wasn't marked as a rational tableau already and if we may | |||
965 | * need to undo changes, then arrange for the marking to be undone | |||
966 | * during the undo. | |||
967 | */ | |||
968 | int isl_tab_mark_rational(struct isl_tab *tab) | |||
969 | { | |||
970 | if (!tab) | |||
971 | return -1; | |||
972 | if (!tab->rational && tab->need_undo) | |||
973 | if (isl_tab_push(tab, isl_tab_undo_rational) < 0) | |||
974 | return -1; | |||
975 | tab->rational = 1; | |||
976 | return 0; | |||
977 | } | |||
978 | ||||
979 | int isl_tab_mark_empty(struct isl_tab *tab) | |||
980 | { | |||
981 | if (!tab) | |||
982 | return -1; | |||
983 | if (!tab->empty && tab->need_undo) | |||
984 | if (isl_tab_push(tab, isl_tab_undo_empty) < 0) | |||
985 | return -1; | |||
986 | tab->empty = 1; | |||
987 | return 0; | |||
988 | } | |||
989 | ||||
990 | int isl_tab_freeze_constraint(struct isl_tab *tab, int con) | |||
991 | { | |||
992 | struct isl_tab_var *var; | |||
993 | ||||
994 | if (!tab) | |||
995 | return -1; | |||
996 | ||||
997 | var = &tab->con[con]; | |||
998 | if (var->frozen) | |||
999 | return 0; | |||
1000 | if (var->index < 0) | |||
1001 | return 0; | |||
1002 | var->frozen = 1; | |||
1003 | ||||
1004 | if (tab->need_undo) | |||
1005 | return isl_tab_push_var(tab, isl_tab_undo_freeze, var); | |||
1006 | ||||
1007 | return 0; | |||
1008 | } | |||
1009 | ||||
1010 | /* Update the rows signs after a pivot of "row" and "col", with "row_sgn" | |||
1011 | * the original sign of the pivot element. | |||
1012 | * We only keep track of row signs during PILP solving and in this case | |||
1013 | * we only pivot a row with negative sign (meaning the value is always | |||
1014 | * non-positive) using a positive pivot element. | |||
1015 | * | |||
1016 | * For each row j, the new value of the parametric constant is equal to | |||
1017 | * | |||
1018 | * a_j0 - a_jc a_r0/a_rc | |||
1019 | * | |||
1020 | * where a_j0 is the original parametric constant, a_rc is the pivot element, | |||
1021 | * a_r0 is the parametric constant of the pivot row and a_jc is the | |||
1022 | * pivot column entry of the row j. | |||
1023 | * Since a_r0 is non-positive and a_rc is positive, the sign of row j | |||
1024 | * remains the same if a_jc has the same sign as the row j or if | |||
1025 | * a_jc is zero. In all other cases, we reset the sign to "unknown". | |||
1026 | */ | |||
1027 | static void update_row_sign(struct isl_tab *tab, int row, int col, int row_sgn) | |||
1028 | { | |||
1029 | int i; | |||
1030 | struct isl_mat *mat = tab->mat; | |||
1031 | unsigned off = 2 + tab->M; | |||
1032 | ||||
1033 | if (!tab->row_sign) | |||
1034 | return; | |||
1035 | ||||
1036 | if (tab->row_sign[row] == 0) | |||
1037 | return; | |||
1038 | isl_assert(mat->ctx, row_sgn > 0, return)do { if (row_sgn > 0) break; do { isl_handle_error(mat-> ctx, isl_error_unknown, "Assertion \"" "row_sgn > 0" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1038); return; } while (0); } while (0); | |||
1039 | isl_assert(mat->ctx, tab->row_sign[row] == isl_tab_row_neg, return)do { if (tab->row_sign[row] == isl_tab_row_neg) break; do { isl_handle_error(mat->ctx, isl_error_unknown, "Assertion \"" "tab->row_sign[row] == isl_tab_row_neg" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1039); return; } while (0); } while (0); | |||
1040 | tab->row_sign[row] = isl_tab_row_pos; | |||
1041 | for (i = 0; i < tab->n_row; ++i) { | |||
1042 | int s; | |||
1043 | if (i == row) | |||
1044 | continue; | |||
1045 | s = isl_int_sgn(mat->row[i][off + col])isl_sioimath_sgn(*(mat->row[i][off + col])); | |||
1046 | if (!s) | |||
1047 | continue; | |||
1048 | if (!tab->row_sign[i]) | |||
1049 | continue; | |||
1050 | if (s < 0 && tab->row_sign[i] == isl_tab_row_neg) | |||
1051 | continue; | |||
1052 | if (s > 0 && tab->row_sign[i] == isl_tab_row_pos) | |||
1053 | continue; | |||
1054 | tab->row_sign[i] = isl_tab_row_unknown; | |||
1055 | } | |||
1056 | } | |||
1057 | ||||
1058 | /* Given a row number "row" and a column number "col", pivot the tableau | |||
1059 | * such that the associated variables are interchanged. | |||
1060 | * The given row in the tableau expresses | |||
1061 | * | |||
1062 | * x_r = a_r0 + \sum_i a_ri x_i | |||
1063 | * | |||
1064 | * or | |||
1065 | * | |||
1066 | * x_c = 1/a_rc x_r - a_r0/a_rc + sum_{i \ne r} -a_ri/a_rc | |||
1067 | * | |||
1068 | * Substituting this equality into the other rows | |||
1069 | * | |||
1070 | * x_j = a_j0 + \sum_i a_ji x_i | |||
1071 | * | |||
1072 | * with a_jc \ne 0, we obtain | |||
1073 | * | |||
1074 | * x_j = a_jc/a_rc x_r + a_j0 - a_jc a_r0/a_rc + sum a_ji - a_jc a_ri/a_rc | |||
1075 | * | |||
1076 | * The tableau | |||
1077 | * | |||
1078 | * n_rc/d_r n_ri/d_r | |||
1079 | * n_jc/d_j n_ji/d_j | |||
1080 | * | |||
1081 | * where i is any other column and j is any other row, | |||
1082 | * is therefore transformed into | |||
1083 | * | |||
1084 | * s(n_rc)d_r/|n_rc| -s(n_rc)n_ri/|n_rc| | |||
1085 | * s(n_rc)d_r n_jc/(|n_rc| d_j) (n_ji |n_rc| - s(n_rc)n_jc n_ri)/(|n_rc| d_j) | |||
1086 | * | |||
1087 | * The transformation is performed along the following steps | |||
1088 | * | |||
1089 | * d_r/n_rc n_ri/n_rc | |||
1090 | * n_jc/d_j n_ji/d_j | |||
1091 | * | |||
1092 | * s(n_rc)d_r/|n_rc| -s(n_rc)n_ri/|n_rc| | |||
1093 | * n_jc/d_j n_ji/d_j | |||
1094 | * | |||
1095 | * s(n_rc)d_r/|n_rc| -s(n_rc)n_ri/|n_rc| | |||
1096 | * n_jc/(|n_rc| d_j) n_ji/(|n_rc| d_j) | |||
1097 | * | |||
1098 | * s(n_rc)d_r/|n_rc| -s(n_rc)n_ri/|n_rc| | |||
1099 | * n_jc/(|n_rc| d_j) (n_ji |n_rc|)/(|n_rc| d_j) | |||
1100 | * | |||
1101 | * s(n_rc)d_r/|n_rc| -s(n_rc)n_ri/|n_rc| | |||
1102 | * n_jc/(|n_rc| d_j) (n_ji |n_rc| - s(n_rc)n_jc n_ri)/(|n_rc| d_j) | |||
1103 | * | |||
1104 | * s(n_rc)d_r/|n_rc| -s(n_rc)n_ri/|n_rc| | |||
1105 | * s(n_rc)d_r n_jc/(|n_rc| d_j) (n_ji |n_rc| - s(n_rc)n_jc n_ri)/(|n_rc| d_j) | |||
1106 | * | |||
1107 | */ | |||
1108 | int isl_tab_pivot(struct isl_tab *tab, int row, int col) | |||
1109 | { | |||
1110 | int i, j; | |||
1111 | int sgn; | |||
1112 | int t; | |||
1113 | isl_ctx *ctx; | |||
1114 | struct isl_mat *mat = tab->mat; | |||
1115 | struct isl_tab_var *var; | |||
1116 | unsigned off = 2 + tab->M; | |||
1117 | ||||
1118 | ctx = isl_tab_get_ctx(tab); | |||
1119 | if (isl_ctx_next_operation(ctx) < 0) | |||
1120 | return -1; | |||
1121 | ||||
1122 | isl_int_swap(mat->row[row][0], mat->row[row][off + col])isl_sioimath_swap((mat->row[row][0]), (mat->row[row][off + col])); | |||
1123 | sgn = isl_int_sgn(mat->row[row][0])isl_sioimath_sgn(*(mat->row[row][0])); | |||
1124 | if (sgn < 0) { | |||
1125 | isl_int_neg(mat->row[row][0], mat->row[row][0])isl_sioimath_neg((mat->row[row][0]), *(mat->row[row][0] )); | |||
1126 | isl_int_neg(mat->row[row][off + col], mat->row[row][off + col])isl_sioimath_neg((mat->row[row][off + col]), *(mat->row [row][off + col])); | |||
1127 | } else | |||
1128 | for (j = 0; j < off - 1 + tab->n_col; ++j) { | |||
1129 | if (j == off - 1 + col) | |||
1130 | continue; | |||
1131 | isl_int_neg(mat->row[row][1 + j], mat->row[row][1 + j])isl_sioimath_neg((mat->row[row][1 + j]), *(mat->row[row ][1 + j])); | |||
1132 | } | |||
1133 | if (!isl_int_is_one(mat->row[row][0])(isl_sioimath_cmp_si(*(mat->row[row][0]), 1) == 0)) | |||
1134 | isl_seq_normalize(mat->ctx, mat->row[row], off + tab->n_col); | |||
1135 | for (i = 0; i < tab->n_row; ++i) { | |||
1136 | if (i == row) | |||
1137 | continue; | |||
1138 | if (isl_int_is_zero(mat->row[i][off + col])(isl_sioimath_sgn(*(mat->row[i][off + col])) == 0)) | |||
1139 | continue; | |||
1140 | isl_int_mul(mat->row[i][0], mat->row[i][0], mat->row[row][0])isl_sioimath_mul((mat->row[i][0]), *(mat->row[i][0]), * (mat->row[row][0])); | |||
1141 | for (j = 0; j < off - 1 + tab->n_col; ++j) { | |||
1142 | if (j == off - 1 + col) | |||
1143 | continue; | |||
1144 | isl_int_mul(mat->row[i][1 + j],isl_sioimath_mul((mat->row[i][1 + j]), *(mat->row[i][1 + j]), *(mat->row[row][0])) | |||
1145 | mat->row[i][1 + j], mat->row[row][0])isl_sioimath_mul((mat->row[i][1 + j]), *(mat->row[i][1 + j]), *(mat->row[row][0])); | |||
1146 | isl_int_addmul(mat->row[i][1 + j],isl_sioimath_addmul((mat->row[i][1 + j]), *(mat->row[i] [off + col]), *(mat->row[row][1 + j])) | |||
1147 | mat->row[i][off + col], mat->row[row][1 + j])isl_sioimath_addmul((mat->row[i][1 + j]), *(mat->row[i] [off + col]), *(mat->row[row][1 + j])); | |||
1148 | } | |||
1149 | isl_int_mul(mat->row[i][off + col],isl_sioimath_mul((mat->row[i][off + col]), *(mat->row[i ][off + col]), *(mat->row[row][off + col])) | |||
1150 | mat->row[i][off + col], mat->row[row][off + col])isl_sioimath_mul((mat->row[i][off + col]), *(mat->row[i ][off + col]), *(mat->row[row][off + col])); | |||
1151 | if (!isl_int_is_one(mat->row[i][0])(isl_sioimath_cmp_si(*(mat->row[i][0]), 1) == 0)) | |||
1152 | isl_seq_normalize(mat->ctx, mat->row[i], off + tab->n_col); | |||
1153 | } | |||
1154 | t = tab->row_var[row]; | |||
1155 | tab->row_var[row] = tab->col_var[col]; | |||
1156 | tab->col_var[col] = t; | |||
1157 | var = isl_tab_var_from_row(tab, row); | |||
1158 | var->is_row = 1; | |||
1159 | var->index = row; | |||
1160 | var = var_from_col(tab, col); | |||
1161 | var->is_row = 0; | |||
1162 | var->index = col; | |||
1163 | update_row_sign(tab, row, col, sgn); | |||
1164 | if (tab->in_undo) | |||
1165 | return 0; | |||
1166 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
1167 | if (isl_int_is_zero(mat->row[i][off + col])(isl_sioimath_sgn(*(mat->row[i][off + col])) == 0)) | |||
1168 | continue; | |||
1169 | if (!isl_tab_var_from_row(tab, i)->frozen && | |||
1170 | isl_tab_row_is_redundant(tab, i)) { | |||
1171 | int redo = isl_tab_mark_redundant(tab, i); | |||
1172 | if (redo < 0) | |||
1173 | return -1; | |||
1174 | if (redo) | |||
1175 | --i; | |||
1176 | } | |||
1177 | } | |||
1178 | return 0; | |||
1179 | } | |||
1180 | ||||
1181 | /* If "var" represents a column variable, then pivot is up (sgn > 0) | |||
1182 | * or down (sgn < 0) to a row. The variable is assumed not to be | |||
1183 | * unbounded in the specified direction. | |||
1184 | * If sgn = 0, then the variable is unbounded in both directions, | |||
1185 | * and we pivot with any row we can find. | |||
1186 | */ | |||
1187 | static int to_row(struct isl_tab *tab, struct isl_tab_var *var, int sign) WARN_UNUSED__attribute__((__warn_unused_result__)); | |||
1188 | static int to_row(struct isl_tab *tab, struct isl_tab_var *var, int sign) | |||
1189 | { | |||
1190 | int r; | |||
1191 | unsigned off = 2 + tab->M; | |||
1192 | ||||
1193 | if (var->is_row) | |||
1194 | return 0; | |||
1195 | ||||
1196 | if (sign == 0) { | |||
1197 | for (r = tab->n_redundant; r < tab->n_row; ++r) | |||
1198 | if (!isl_int_is_zero(tab->mat->row[r][off+var->index])(isl_sioimath_sgn(*(tab->mat->row[r][off+var->index] )) == 0)) | |||
1199 | break; | |||
1200 | isl_assert(tab->mat->ctx, r < tab->n_row, return -1)do { if (r < tab->n_row) break; do { isl_handle_error(tab ->mat->ctx, isl_error_unknown, "Assertion \"" "r < tab->n_row" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1200); return -1; } while (0); } while (0); | |||
1201 | } else { | |||
1202 | r = pivot_row(tab, NULL((void*)0), sign, var->index); | |||
1203 | isl_assert(tab->mat->ctx, r >= 0, return -1)do { if (r >= 0) break; do { isl_handle_error(tab->mat-> ctx, isl_error_unknown, "Assertion \"" "r >= 0" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1203); return -1; } while (0); } while (0); | |||
1204 | } | |||
1205 | ||||
1206 | return isl_tab_pivot(tab, r, var->index); | |||
1207 | } | |||
1208 | ||||
1209 | /* Check whether all variables that are marked as non-negative | |||
1210 | * also have a non-negative sample value. This function is not | |||
1211 | * called from the current code but is useful during debugging. | |||
1212 | */ | |||
1213 | static void check_table(struct isl_tab *tab) __attribute__ ((unused)); | |||
1214 | static void check_table(struct isl_tab *tab) | |||
1215 | { | |||
1216 | int i; | |||
1217 | ||||
1218 | if (tab->empty) | |||
1219 | return; | |||
1220 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
1221 | struct isl_tab_var *var; | |||
1222 | var = isl_tab_var_from_row(tab, i); | |||
1223 | if (!var->is_nonneg) | |||
1224 | continue; | |||
1225 | if (tab->M) { | |||
1226 | isl_assert(tab->mat->ctx,do { if (!(isl_sioimath_sgn(*(tab->mat->row[i][2])) < 0)) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "!(isl_sioimath_sgn(*(tab->mat->row[i][2])) < 0)" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1227); abort(); } while (0); } while (0) | |||
1227 | !isl_int_is_neg(tab->mat->row[i][2]), abort())do { if (!(isl_sioimath_sgn(*(tab->mat->row[i][2])) < 0)) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "!(isl_sioimath_sgn(*(tab->mat->row[i][2])) < 0)" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1227); abort(); } while (0); } while (0); | |||
1228 | if (isl_int_is_pos(tab->mat->row[i][2])(isl_sioimath_sgn(*(tab->mat->row[i][2])) > 0)) | |||
1229 | continue; | |||
1230 | } | |||
1231 | isl_assert(tab->mat->ctx, !isl_int_is_neg(tab->mat->row[i][1]),do { if (!(isl_sioimath_sgn(*(tab->mat->row[i][1])) < 0)) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "!(isl_sioimath_sgn(*(tab->mat->row[i][1])) < 0)" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1232); abort(); } while (0); } while (0) | |||
1232 | abort())do { if (!(isl_sioimath_sgn(*(tab->mat->row[i][1])) < 0)) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "!(isl_sioimath_sgn(*(tab->mat->row[i][1])) < 0)" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1232); abort(); } while (0); } while (0); | |||
1233 | } | |||
1234 | } | |||
1235 | ||||
1236 | /* Return the sign of the maximal value of "var". | |||
1237 | * If the sign is not negative, then on return from this function, | |||
1238 | * the sample value will also be non-negative. | |||
1239 | * | |||
1240 | * If "var" is manifestly unbounded wrt positive values, we are done. | |||
1241 | * Otherwise, we pivot the variable up to a row if needed | |||
1242 | * Then we continue pivoting down until either | |||
1243 | * - no more down pivots can be performed | |||
1244 | * - the sample value is positive | |||
1245 | * - the variable is pivoted into a manifestly unbounded column | |||
1246 | */ | |||
1247 | static int sign_of_max(struct isl_tab *tab, struct isl_tab_var *var) | |||
1248 | { | |||
1249 | int row, col; | |||
1250 | ||||
1251 | if (max_is_manifestly_unbounded(tab, var)) | |||
1252 | return 1; | |||
1253 | if (to_row(tab, var, 1) < 0) | |||
1254 | return -2; | |||
1255 | while (!isl_int_is_pos(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) > 0)) { | |||
1256 | find_pivot(tab, var, var, 1, &row, &col); | |||
1257 | if (row == -1) | |||
1258 | return isl_int_sgn(tab->mat->row[var->index][1])isl_sioimath_sgn(*(tab->mat->row[var->index][1])); | |||
1259 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1260 | return -2; | |||
1261 | if (!var->is_row) /* manifestly unbounded */ | |||
1262 | return 1; | |||
1263 | } | |||
1264 | return 1; | |||
1265 | } | |||
1266 | ||||
1267 | int isl_tab_sign_of_max(struct isl_tab *tab, int con) | |||
1268 | { | |||
1269 | struct isl_tab_var *var; | |||
1270 | ||||
1271 | if (!tab) | |||
1272 | return -2; | |||
1273 | ||||
1274 | var = &tab->con[con]; | |||
1275 | isl_assert(tab->mat->ctx, !var->is_redundant, return -2)do { if (!var->is_redundant) break; do { isl_handle_error( tab->mat->ctx, isl_error_unknown, "Assertion \"" "!var->is_redundant" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1275); return -2; } while (0); } while (0); | |||
1276 | isl_assert(tab->mat->ctx, !var->is_zero, return -2)do { if (!var->is_zero) break; do { isl_handle_error(tab-> mat->ctx, isl_error_unknown, "Assertion \"" "!var->is_zero" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1276); return -2; } while (0); } while (0); | |||
1277 | ||||
1278 | return sign_of_max(tab, var); | |||
1279 | } | |||
1280 | ||||
1281 | static int row_is_neg(struct isl_tab *tab, int row) | |||
1282 | { | |||
1283 | if (!tab->M) | |||
1284 | return isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0); | |||
1285 | if (isl_int_is_pos(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) > 0)) | |||
1286 | return 0; | |||
1287 | if (isl_int_is_neg(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) < 0)) | |||
1288 | return 1; | |||
1289 | return isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0); | |||
1290 | } | |||
1291 | ||||
1292 | static int row_sgn(struct isl_tab *tab, int row) | |||
1293 | { | |||
1294 | if (!tab->M) | |||
1295 | return isl_int_sgn(tab->mat->row[row][1])isl_sioimath_sgn(*(tab->mat->row[row][1])); | |||
1296 | if (!isl_int_is_zero(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) == 0)) | |||
1297 | return isl_int_sgn(tab->mat->row[row][2])isl_sioimath_sgn(*(tab->mat->row[row][2])); | |||
1298 | else | |||
1299 | return isl_int_sgn(tab->mat->row[row][1])isl_sioimath_sgn(*(tab->mat->row[row][1])); | |||
1300 | } | |||
1301 | ||||
1302 | /* Perform pivots until the row variable "var" has a non-negative | |||
1303 | * sample value or until no more upward pivots can be performed. | |||
1304 | * Return the sign of the sample value after the pivots have been | |||
1305 | * performed. | |||
1306 | */ | |||
1307 | static int restore_row(struct isl_tab *tab, struct isl_tab_var *var) | |||
1308 | { | |||
1309 | int row, col; | |||
1310 | ||||
1311 | while (row_is_neg(tab, var->index)) { | |||
1312 | find_pivot(tab, var, var, 1, &row, &col); | |||
1313 | if (row == -1) | |||
1314 | break; | |||
1315 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1316 | return -2; | |||
1317 | if (!var->is_row) /* manifestly unbounded */ | |||
1318 | return 1; | |||
1319 | } | |||
1320 | return row_sgn(tab, var->index); | |||
1321 | } | |||
1322 | ||||
1323 | /* Perform pivots until we are sure that the row variable "var" | |||
1324 | * can attain non-negative values. After return from this | |||
1325 | * function, "var" is still a row variable, but its sample | |||
1326 | * value may not be non-negative, even if the function returns 1. | |||
1327 | */ | |||
1328 | static int at_least_zero(struct isl_tab *tab, struct isl_tab_var *var) | |||
1329 | { | |||
1330 | int row, col; | |||
1331 | ||||
1332 | while (isl_int_is_neg(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) < 0)) { | |||
1333 | find_pivot(tab, var, var, 1, &row, &col); | |||
1334 | if (row == -1) | |||
1335 | break; | |||
1336 | if (row == var->index) /* manifestly unbounded */ | |||
1337 | return 1; | |||
1338 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1339 | return -1; | |||
1340 | } | |||
1341 | return !isl_int_is_neg(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) < 0); | |||
1342 | } | |||
1343 | ||||
1344 | /* Return a negative value if "var" can attain negative values. | |||
1345 | * Return a non-negative value otherwise. | |||
1346 | * | |||
1347 | * If "var" is manifestly unbounded wrt negative values, we are done. | |||
1348 | * Otherwise, if var is in a column, we can pivot it down to a row. | |||
1349 | * Then we continue pivoting down until either | |||
1350 | * - the pivot would result in a manifestly unbounded column | |||
1351 | * => we don't perform the pivot, but simply return -1 | |||
1352 | * - no more down pivots can be performed | |||
1353 | * - the sample value is negative | |||
1354 | * If the sample value becomes negative and the variable is supposed | |||
1355 | * to be nonnegative, then we undo the last pivot. | |||
1356 | * However, if the last pivot has made the pivoting variable | |||
1357 | * obviously redundant, then it may have moved to another row. | |||
1358 | * In that case we look for upward pivots until we reach a non-negative | |||
1359 | * value again. | |||
1360 | */ | |||
1361 | static int sign_of_min(struct isl_tab *tab, struct isl_tab_var *var) | |||
1362 | { | |||
1363 | int row, col; | |||
1364 | struct isl_tab_var *pivot_var = NULL((void*)0); | |||
1365 | ||||
1366 | if (min_is_manifestly_unbounded(tab, var)) | |||
1367 | return -1; | |||
1368 | if (!var->is_row) { | |||
1369 | col = var->index; | |||
1370 | row = pivot_row(tab, NULL((void*)0), -1, col); | |||
1371 | pivot_var = var_from_col(tab, col); | |||
1372 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1373 | return -2; | |||
1374 | if (var->is_redundant) | |||
1375 | return 0; | |||
1376 | if (isl_int_is_neg(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) < 0)) { | |||
1377 | if (var->is_nonneg) { | |||
1378 | if (!pivot_var->is_redundant && | |||
1379 | pivot_var->index == row) { | |||
1380 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1381 | return -2; | |||
1382 | } else | |||
1383 | if (restore_row(tab, var) < -1) | |||
1384 | return -2; | |||
1385 | } | |||
1386 | return -1; | |||
1387 | } | |||
1388 | } | |||
1389 | if (var->is_redundant) | |||
1390 | return 0; | |||
1391 | while (!isl_int_is_neg(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) < 0)) { | |||
1392 | find_pivot(tab, var, var, -1, &row, &col); | |||
1393 | if (row == var->index) | |||
1394 | return -1; | |||
1395 | if (row == -1) | |||
1396 | return isl_int_sgn(tab->mat->row[var->index][1])isl_sioimath_sgn(*(tab->mat->row[var->index][1])); | |||
1397 | pivot_var = var_from_col(tab, col); | |||
1398 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1399 | return -2; | |||
1400 | if (var->is_redundant) | |||
1401 | return 0; | |||
1402 | } | |||
1403 | if (pivot_var && var->is_nonneg) { | |||
1404 | /* pivot back to non-negative value */ | |||
1405 | if (!pivot_var->is_redundant && pivot_var->index == row) { | |||
1406 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1407 | return -2; | |||
1408 | } else | |||
1409 | if (restore_row(tab, var) < -1) | |||
1410 | return -2; | |||
1411 | } | |||
1412 | return -1; | |||
1413 | } | |||
1414 | ||||
1415 | static int row_at_most_neg_one(struct isl_tab *tab, int row) | |||
1416 | { | |||
1417 | if (tab->M) { | |||
1418 | if (isl_int_is_pos(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) > 0)) | |||
1419 | return 0; | |||
1420 | if (isl_int_is_neg(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) < 0)) | |||
1421 | return 1; | |||
1422 | } | |||
1423 | return isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0) && | |||
1424 | isl_int_abs_ge(tab->mat->row[row][1],(isl_sioimath_abs_cmp(*(tab->mat->row[row][1]), *(tab-> mat->row[row][0])) >= 0) | |||
1425 | tab->mat->row[row][0])(isl_sioimath_abs_cmp(*(tab->mat->row[row][1]), *(tab-> mat->row[row][0])) >= 0); | |||
1426 | } | |||
1427 | ||||
1428 | /* Return 1 if "var" can attain values <= -1. | |||
1429 | * Return 0 otherwise. | |||
1430 | * | |||
1431 | * If the variable "var" is supposed to be non-negative (is_nonneg is set), | |||
1432 | * then the sample value of "var" is assumed to be non-negative when the | |||
1433 | * the function is called. If 1 is returned then the constraint | |||
1434 | * is not redundant and the sample value is made non-negative again before | |||
1435 | * the function returns. | |||
1436 | */ | |||
1437 | int isl_tab_min_at_most_neg_one(struct isl_tab *tab, struct isl_tab_var *var) | |||
1438 | { | |||
1439 | int row, col; | |||
1440 | struct isl_tab_var *pivot_var; | |||
1441 | ||||
1442 | if (min_is_manifestly_unbounded(tab, var)) | |||
1443 | return 1; | |||
1444 | if (!var->is_row) { | |||
1445 | col = var->index; | |||
1446 | row = pivot_row(tab, NULL((void*)0), -1, col); | |||
1447 | pivot_var = var_from_col(tab, col); | |||
1448 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1449 | return -1; | |||
1450 | if (var->is_redundant) | |||
1451 | return 0; | |||
1452 | if (row_at_most_neg_one(tab, var->index)) { | |||
1453 | if (var->is_nonneg) { | |||
1454 | if (!pivot_var->is_redundant && | |||
1455 | pivot_var->index == row) { | |||
1456 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1457 | return -1; | |||
1458 | } else | |||
1459 | if (restore_row(tab, var) < -1) | |||
1460 | return -1; | |||
1461 | } | |||
1462 | return 1; | |||
1463 | } | |||
1464 | } | |||
1465 | if (var->is_redundant) | |||
1466 | return 0; | |||
1467 | do { | |||
1468 | find_pivot(tab, var, var, -1, &row, &col); | |||
1469 | if (row == var->index) { | |||
1470 | if (var->is_nonneg && restore_row(tab, var) < -1) | |||
1471 | return -1; | |||
1472 | return 1; | |||
1473 | } | |||
1474 | if (row == -1) | |||
1475 | return 0; | |||
1476 | pivot_var = var_from_col(tab, col); | |||
1477 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1478 | return -1; | |||
1479 | if (var->is_redundant) | |||
1480 | return 0; | |||
1481 | } while (!row_at_most_neg_one(tab, var->index)); | |||
1482 | if (var->is_nonneg) { | |||
1483 | /* pivot back to non-negative value */ | |||
1484 | if (!pivot_var->is_redundant && pivot_var->index == row) | |||
1485 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1486 | return -1; | |||
1487 | if (restore_row(tab, var) < -1) | |||
1488 | return -1; | |||
1489 | } | |||
1490 | return 1; | |||
1491 | } | |||
1492 | ||||
1493 | /* Return 1 if "var" can attain values >= 1. | |||
1494 | * Return 0 otherwise. | |||
1495 | */ | |||
1496 | static int at_least_one(struct isl_tab *tab, struct isl_tab_var *var) | |||
1497 | { | |||
1498 | int row, col; | |||
1499 | isl_int *r; | |||
1500 | ||||
1501 | if (max_is_manifestly_unbounded(tab, var)) | |||
1502 | return 1; | |||
1503 | if (to_row(tab, var, 1) < 0) | |||
1504 | return -1; | |||
1505 | r = tab->mat->row[var->index]; | |||
1506 | while (isl_int_lt(r[1], r[0])(isl_sioimath_cmp(*(r[1]), *(r[0])) < 0)) { | |||
1507 | find_pivot(tab, var, var, 1, &row, &col); | |||
1508 | if (row == -1) | |||
1509 | return isl_int_ge(r[1], r[0])(isl_sioimath_cmp(*(r[1]), *(r[0])) >= 0); | |||
1510 | if (row == var->index) /* manifestly unbounded */ | |||
1511 | return 1; | |||
1512 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1513 | return -1; | |||
1514 | } | |||
1515 | return 1; | |||
1516 | } | |||
1517 | ||||
1518 | static void swap_cols(struct isl_tab *tab, int col1, int col2) | |||
1519 | { | |||
1520 | int t; | |||
1521 | unsigned off = 2 + tab->M; | |||
1522 | t = tab->col_var[col1]; | |||
1523 | tab->col_var[col1] = tab->col_var[col2]; | |||
1524 | tab->col_var[col2] = t; | |||
1525 | var_from_col(tab, col1)->index = col1; | |||
1526 | var_from_col(tab, col2)->index = col2; | |||
1527 | tab->mat = isl_mat_swap_cols(tab->mat, off + col1, off + col2); | |||
1528 | } | |||
1529 | ||||
1530 | /* Mark column with index "col" as representing a zero variable. | |||
1531 | * If we may need to undo the operation the column is kept, | |||
1532 | * but no longer considered. | |||
1533 | * Otherwise, the column is simply removed. | |||
1534 | * | |||
1535 | * The column may be interchanged with some other column. If it | |||
1536 | * is interchanged with a later column, return 1. Otherwise return 0. | |||
1537 | * If the columns are checked in order in the calling function, | |||
1538 | * then a return value of 1 means that the column with the given | |||
1539 | * column number may now contain a different column that | |||
1540 | * hasn't been checked yet. | |||
1541 | */ | |||
1542 | int isl_tab_kill_col(struct isl_tab *tab, int col) | |||
1543 | { | |||
1544 | var_from_col(tab, col)->is_zero = 1; | |||
1545 | if (tab->need_undo) { | |||
1546 | if (isl_tab_push_var(tab, isl_tab_undo_zero, | |||
1547 | var_from_col(tab, col)) < 0) | |||
1548 | return -1; | |||
1549 | if (col != tab->n_dead) | |||
1550 | swap_cols(tab, col, tab->n_dead); | |||
1551 | tab->n_dead++; | |||
1552 | return 0; | |||
1553 | } else { | |||
1554 | if (col != tab->n_col - 1) | |||
1555 | swap_cols(tab, col, tab->n_col - 1); | |||
1556 | var_from_col(tab, tab->n_col - 1)->index = -1; | |||
1557 | tab->n_col--; | |||
1558 | return 1; | |||
1559 | } | |||
1560 | } | |||
1561 | ||||
1562 | static int row_is_manifestly_non_integral(struct isl_tab *tab, int row) | |||
1563 | { | |||
1564 | unsigned off = 2 + tab->M; | |||
1565 | ||||
1566 | if (tab->M && !isl_int_eq(tab->mat->row[row][2],(isl_sioimath_cmp(*(tab->mat->row[row][2]), *(tab->mat ->row[row][0])) == 0) | |||
1567 | tab->mat->row[row][0])(isl_sioimath_cmp(*(tab->mat->row[row][2]), *(tab->mat ->row[row][0])) == 0)) | |||
1568 | return 0; | |||
1569 | if (isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead, | |||
1570 | tab->n_col - tab->n_dead) != -1) | |||
1571 | return 0; | |||
1572 | ||||
1573 | return !isl_int_is_divisible_by(tab->mat->row[row][1],isl_sioimath_is_divisible_by(*(tab->mat->row[row][1]), * (tab->mat->row[row][0])) | |||
1574 | tab->mat->row[row][0])isl_sioimath_is_divisible_by(*(tab->mat->row[row][1]), * (tab->mat->row[row][0])); | |||
1575 | } | |||
1576 | ||||
1577 | /* For integer tableaus, check if any of the coordinates are stuck | |||
1578 | * at a non-integral value. | |||
1579 | */ | |||
1580 | static int tab_is_manifestly_empty(struct isl_tab *tab) | |||
1581 | { | |||
1582 | int i; | |||
1583 | ||||
1584 | if (tab->empty) | |||
1585 | return 1; | |||
1586 | if (tab->rational) | |||
1587 | return 0; | |||
1588 | ||||
1589 | for (i = 0; i < tab->n_var; ++i) { | |||
1590 | if (!tab->var[i].is_row) | |||
1591 | continue; | |||
1592 | if (row_is_manifestly_non_integral(tab, tab->var[i].index)) | |||
1593 | return 1; | |||
1594 | } | |||
1595 | ||||
1596 | return 0; | |||
1597 | } | |||
1598 | ||||
1599 | /* Row variable "var" is non-negative and cannot attain any values | |||
1600 | * larger than zero. This means that the coefficients of the unrestricted | |||
1601 | * column variables are zero and that the coefficients of the non-negative | |||
1602 | * column variables are zero or negative. | |||
1603 | * Each of the non-negative variables with a negative coefficient can | |||
1604 | * then also be written as the negative sum of non-negative variables | |||
1605 | * and must therefore also be zero. | |||
1606 | */ | |||
1607 | static int close_row(struct isl_tab *tab, struct isl_tab_var *var) WARN_UNUSED__attribute__((__warn_unused_result__)); | |||
1608 | static int close_row(struct isl_tab *tab, struct isl_tab_var *var) | |||
1609 | { | |||
1610 | int j; | |||
1611 | struct isl_mat *mat = tab->mat; | |||
1612 | unsigned off = 2 + tab->M; | |||
1613 | ||||
1614 | isl_assert(tab->mat->ctx, var->is_nonneg, return -1)do { if (var->is_nonneg) break; do { isl_handle_error(tab-> mat->ctx, isl_error_unknown, "Assertion \"" "var->is_nonneg" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1614); return -1; } while (0); } while (0); | |||
1615 | var->is_zero = 1; | |||
1616 | if (tab->need_undo) | |||
1617 | if (isl_tab_push_var(tab, isl_tab_undo_zero, var) < 0) | |||
1618 | return -1; | |||
1619 | for (j = tab->n_dead; j < tab->n_col; ++j) { | |||
1620 | int recheck; | |||
1621 | if (isl_int_is_zero(mat->row[var->index][off + j])(isl_sioimath_sgn(*(mat->row[var->index][off + j])) == 0 )) | |||
1622 | continue; | |||
1623 | isl_assert(tab->mat->ctx,do { if ((isl_sioimath_sgn(*(mat->row[var->index][off + j])) < 0)) break; do { isl_handle_error(tab->mat->ctx , isl_error_unknown, "Assertion \"" "(isl_sioimath_sgn(*(mat->row[var->index][off + j])) < 0)" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1624); return -1; } while (0); } while (0) | |||
1624 | isl_int_is_neg(mat->row[var->index][off + j]), return -1)do { if ((isl_sioimath_sgn(*(mat->row[var->index][off + j])) < 0)) break; do { isl_handle_error(tab->mat->ctx , isl_error_unknown, "Assertion \"" "(isl_sioimath_sgn(*(mat->row[var->index][off + j])) < 0)" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1624); return -1; } while (0); } while (0); | |||
1625 | recheck = isl_tab_kill_col(tab, j); | |||
1626 | if (recheck < 0) | |||
1627 | return -1; | |||
1628 | if (recheck) | |||
1629 | --j; | |||
1630 | } | |||
1631 | if (isl_tab_mark_redundant(tab, var->index) < 0) | |||
1632 | return -1; | |||
1633 | if (tab_is_manifestly_empty(tab) && isl_tab_mark_empty(tab) < 0) | |||
1634 | return -1; | |||
1635 | return 0; | |||
1636 | } | |||
1637 | ||||
1638 | /* Add a constraint to the tableau and allocate a row for it. | |||
1639 | * Return the index into the constraint array "con". | |||
1640 | */ | |||
1641 | int isl_tab_allocate_con(struct isl_tab *tab) | |||
1642 | { | |||
1643 | int r; | |||
1644 | ||||
1645 | isl_assert(tab->mat->ctx, tab->n_row < tab->mat->n_row, return -1)do { if (tab->n_row < tab->mat->n_row) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown, "Assertion \"" "tab->n_row < tab->mat->n_row" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1645); return -1; } while (0); } while (0); | |||
1646 | isl_assert(tab->mat->ctx, tab->n_con < tab->max_con, return -1)do { if (tab->n_con < tab->max_con) break; do { isl_handle_error (tab->mat->ctx, isl_error_unknown, "Assertion \"" "tab->n_con < tab->max_con" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1646); return -1; } while (0); } while (0); | |||
1647 | ||||
1648 | r = tab->n_con; | |||
1649 | tab->con[r].index = tab->n_row; | |||
1650 | tab->con[r].is_row = 1; | |||
1651 | tab->con[r].is_nonneg = 0; | |||
1652 | tab->con[r].is_zero = 0; | |||
1653 | tab->con[r].is_redundant = 0; | |||
1654 | tab->con[r].frozen = 0; | |||
1655 | tab->con[r].negated = 0; | |||
1656 | tab->row_var[tab->n_row] = ~r; | |||
1657 | ||||
1658 | tab->n_row++; | |||
1659 | tab->n_con++; | |||
1660 | if (isl_tab_push_var(tab, isl_tab_undo_allocate, &tab->con[r]) < 0) | |||
1661 | return -1; | |||
1662 | ||||
1663 | return r; | |||
1664 | } | |||
1665 | ||||
1666 | /* Move the entries in tab->var up one position, starting at "first", | |||
1667 | * creating room for an extra entry at position "first". | |||
1668 | * Since some of the entries of tab->row_var and tab->col_var contain | |||
1669 | * indices into this array, they have to be updated accordingly. | |||
1670 | */ | |||
1671 | static int var_insert_entry(struct isl_tab *tab, int first) | |||
1672 | { | |||
1673 | int i; | |||
1674 | ||||
1675 | if (tab->n_var >= tab->max_var) | |||
1676 | isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal , "not enough room for new variable", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1677); return -1; } while (0) | |||
1677 | "not enough room for new variable", return -1)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal , "not enough room for new variable", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1677); return -1; } while (0); | |||
1678 | if (first > tab->n_var) | |||
1679 | isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal , "invalid initial position", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1680); return -1; } while (0) | |||
1680 | "invalid initial position", return -1)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal , "invalid initial position", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1680); return -1; } while (0); | |||
1681 | ||||
1682 | for (i = tab->n_var - 1; i >= first; --i) { | |||
1683 | tab->var[i + 1] = tab->var[i]; | |||
1684 | if (tab->var[i + 1].is_row) | |||
1685 | tab->row_var[tab->var[i + 1].index]++; | |||
1686 | else | |||
1687 | tab->col_var[tab->var[i + 1].index]++; | |||
1688 | } | |||
1689 | ||||
1690 | tab->n_var++; | |||
1691 | ||||
1692 | return 0; | |||
1693 | } | |||
1694 | ||||
1695 | /* Drop the entry at position "first" in tab->var, moving all | |||
1696 | * subsequent entries down. | |||
1697 | * Since some of the entries of tab->row_var and tab->col_var contain | |||
1698 | * indices into this array, they have to be updated accordingly. | |||
1699 | */ | |||
1700 | static int var_drop_entry(struct isl_tab *tab, int first) | |||
1701 | { | |||
1702 | int i; | |||
1703 | ||||
1704 | if (first >= tab->n_var) | |||
1705 | isl_die(isl_tab_get_ctx(tab), isl_error_internal,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal , "invalid initial position", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1706); return -1; } while (0) | |||
1706 | "invalid initial position", return -1)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_internal , "invalid initial position", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1706); return -1; } while (0); | |||
1707 | ||||
1708 | tab->n_var--; | |||
1709 | ||||
1710 | for (i = first; i < tab->n_var; ++i) { | |||
1711 | tab->var[i] = tab->var[i + 1]; | |||
1712 | if (tab->var[i + 1].is_row) | |||
1713 | tab->row_var[tab->var[i].index]--; | |||
1714 | else | |||
1715 | tab->col_var[tab->var[i].index]--; | |||
1716 | } | |||
1717 | ||||
1718 | return 0; | |||
1719 | } | |||
1720 | ||||
1721 | /* Add a variable to the tableau at position "r" and allocate a column for it. | |||
1722 | * Return the index into the variable array "var", i.e., "r", | |||
1723 | * or -1 on error. | |||
1724 | */ | |||
1725 | int isl_tab_insert_var(struct isl_tab *tab, int r) | |||
1726 | { | |||
1727 | int i; | |||
1728 | unsigned off = 2 + tab->M; | |||
1729 | ||||
1730 | isl_assert(tab->mat->ctx, tab->n_col < tab->mat->n_col, return -1)do { if (tab->n_col < tab->mat->n_col) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown, "Assertion \"" "tab->n_col < tab->mat->n_col" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1730); return -1; } while (0); } while (0); | |||
1731 | ||||
1732 | if (var_insert_entry(tab, r) < 0) | |||
1733 | return -1; | |||
1734 | ||||
1735 | tab->var[r].index = tab->n_col; | |||
1736 | tab->var[r].is_row = 0; | |||
1737 | tab->var[r].is_nonneg = 0; | |||
1738 | tab->var[r].is_zero = 0; | |||
1739 | tab->var[r].is_redundant = 0; | |||
1740 | tab->var[r].frozen = 0; | |||
1741 | tab->var[r].negated = 0; | |||
1742 | tab->col_var[tab->n_col] = r; | |||
1743 | ||||
1744 | for (i = 0; i < tab->n_row; ++i) | |||
1745 | isl_int_set_si(tab->mat->row[i][off + tab->n_col], 0)isl_sioimath_set_si((tab->mat->row[i][off + tab->n_col ]), 0); | |||
1746 | ||||
1747 | tab->n_col++; | |||
1748 | if (isl_tab_push_var(tab, isl_tab_undo_allocate, &tab->var[r]) < 0) | |||
1749 | return -1; | |||
1750 | ||||
1751 | return r; | |||
1752 | } | |||
1753 | ||||
1754 | /* Add a variable to the tableau and allocate a column for it. | |||
1755 | * Return the index into the variable array "var". | |||
1756 | */ | |||
1757 | int isl_tab_allocate_var(struct isl_tab *tab) | |||
1758 | { | |||
1759 | if (!tab) | |||
1760 | return -1; | |||
1761 | ||||
1762 | return isl_tab_insert_var(tab, tab->n_var); | |||
1763 | } | |||
1764 | ||||
1765 | /* Add a row to the tableau. The row is given as an affine combination | |||
1766 | * of the original variables and needs to be expressed in terms of the | |||
1767 | * column variables. | |||
1768 | * | |||
1769 | * We add each term in turn. | |||
1770 | * If r = n/d_r is the current sum and we need to add k x, then | |||
1771 | * if x is a column variable, we increase the numerator of | |||
1772 | * this column by k d_r | |||
1773 | * if x = f/d_x is a row variable, then the new representation of r is | |||
1774 | * | |||
1775 | * n k f d_x/g n + d_r/g k f m/d_r n + m/d_g k f | |||
1776 | * --- + --- = ------------------- = ------------------- | |||
1777 | * d_r d_r d_r d_x/g m | |||
1778 | * | |||
1779 | * with g the gcd of d_r and d_x and m the lcm of d_r and d_x. | |||
1780 | * | |||
1781 | * If tab->M is set, then, internally, each variable x is represented | |||
1782 | * as x' - M. We then also need no subtract k d_r from the coefficient of M. | |||
1783 | */ | |||
1784 | int isl_tab_add_row(struct isl_tab *tab, isl_int *line) | |||
1785 | { | |||
1786 | int i; | |||
1787 | int r; | |||
1788 | isl_int *row; | |||
1789 | isl_int a, b; | |||
1790 | unsigned off = 2 + tab->M; | |||
1791 | ||||
1792 | r = isl_tab_allocate_con(tab); | |||
1793 | if (r < 0) | |||
1794 | return -1; | |||
1795 | ||||
1796 | isl_int_init(a)isl_sioimath_init((a)); | |||
1797 | isl_int_init(b)isl_sioimath_init((b)); | |||
1798 | row = tab->mat->row[tab->con[r].index]; | |||
1799 | isl_int_set_si(row[0], 1)isl_sioimath_set_si((row[0]), 1); | |||
1800 | isl_int_set(row[1], line[0])isl_sioimath_set((row[1]), *(line[0])); | |||
1801 | isl_seq_clr(row + 2, tab->M + tab->n_col); | |||
1802 | for (i = 0; i < tab->n_var; ++i) { | |||
1803 | if (tab->var[i].is_zero) | |||
1804 | continue; | |||
1805 | if (tab->var[i].is_row) { | |||
1806 | isl_int_lcm(a,isl_sioimath_lcm((a), *(row[0]), *(tab->mat->row[tab-> var[i].index][0])) | |||
1807 | row[0], tab->mat->row[tab->var[i].index][0])isl_sioimath_lcm((a), *(row[0]), *(tab->mat->row[tab-> var[i].index][0])); | |||
1808 | isl_int_swap(a, row[0])isl_sioimath_swap((a), (row[0])); | |||
1809 | isl_int_divexact(a, row[0], a)isl_sioimath_tdiv_q((a), *(row[0]), *(a)); | |||
1810 | isl_int_divexact(b,isl_sioimath_tdiv_q((b), *(row[0]), *(tab->mat->row[tab ->var[i].index][0])) | |||
1811 | row[0], tab->mat->row[tab->var[i].index][0])isl_sioimath_tdiv_q((b), *(row[0]), *(tab->mat->row[tab ->var[i].index][0])); | |||
1812 | isl_int_mul(b, b, line[1 + i])isl_sioimath_mul((b), *(b), *(line[1 + i])); | |||
1813 | isl_seq_combine(row + 1, a, row + 1, | |||
1814 | b, tab->mat->row[tab->var[i].index] + 1, | |||
1815 | 1 + tab->M + tab->n_col); | |||
1816 | } else | |||
1817 | isl_int_addmul(row[off + tab->var[i].index],isl_sioimath_addmul((row[off + tab->var[i].index]), *(line [1 + i]), *(row[0])) | |||
1818 | line[1 + i], row[0])isl_sioimath_addmul((row[off + tab->var[i].index]), *(line [1 + i]), *(row[0])); | |||
1819 | if (tab->M && i >= tab->n_param && i < tab->n_var - tab->n_div) | |||
1820 | isl_int_submul(row[2], line[1 + i], row[0])isl_sioimath_submul((row[2]), *(line[1 + i]), *(row[0])); | |||
1821 | } | |||
1822 | isl_seq_normalize(tab->mat->ctx, row, off + tab->n_col); | |||
1823 | isl_int_clear(a)isl_sioimath_clear((a)); | |||
1824 | isl_int_clear(b)isl_sioimath_clear((b)); | |||
1825 | ||||
1826 | if (tab->row_sign) | |||
1827 | tab->row_sign[tab->con[r].index] = isl_tab_row_unknown; | |||
1828 | ||||
1829 | return r; | |||
1830 | } | |||
1831 | ||||
1832 | static int drop_row(struct isl_tab *tab, int row) | |||
1833 | { | |||
1834 | isl_assert(tab->mat->ctx, ~tab->row_var[row] == tab->n_con - 1, return -1)do { if (~tab->row_var[row] == tab->n_con - 1) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown, "Assertion \"" "~tab->row_var[row] == tab->n_con - 1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1834); return -1; } while (0); } while (0); | |||
1835 | if (row != tab->n_row - 1) | |||
1836 | swap_rows(tab, row, tab->n_row - 1); | |||
1837 | tab->n_row--; | |||
1838 | tab->n_con--; | |||
1839 | return 0; | |||
1840 | } | |||
1841 | ||||
1842 | /* Drop the variable in column "col" along with the column. | |||
1843 | * The column is removed first because it may need to be moved | |||
1844 | * into the last position and this process requires | |||
1845 | * the contents of the col_var array in a state | |||
1846 | * before the removal of the variable. | |||
1847 | */ | |||
1848 | static int drop_col(struct isl_tab *tab, int col) | |||
1849 | { | |||
1850 | int var; | |||
1851 | ||||
1852 | var = tab->col_var[col]; | |||
1853 | if (col != tab->n_col - 1) | |||
1854 | swap_cols(tab, col, tab->n_col - 1); | |||
1855 | tab->n_col--; | |||
1856 | if (var_drop_entry(tab, var) < 0) | |||
1857 | return -1; | |||
1858 | return 0; | |||
1859 | } | |||
1860 | ||||
1861 | /* Add inequality "ineq" and check if it conflicts with the | |||
1862 | * previously added constraints or if it is obviously redundant. | |||
1863 | */ | |||
1864 | int isl_tab_add_ineq(struct isl_tab *tab, isl_int *ineq) | |||
1865 | { | |||
1866 | int r; | |||
1867 | int sgn; | |||
1868 | isl_int cst; | |||
1869 | ||||
1870 | if (!tab) | |||
1871 | return -1; | |||
1872 | if (tab->bmap) { | |||
1873 | struct isl_basic_map *bmap = tab->bmap; | |||
1874 | ||||
1875 | isl_assert(tab->mat->ctx, tab->n_eq == bmap->n_eq, return -1)do { if (tab->n_eq == bmap->n_eq) break; do { isl_handle_error (tab->mat->ctx, isl_error_unknown, "Assertion \"" "tab->n_eq == bmap->n_eq" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1875); return -1; } while (0); } while (0); | |||
1876 | isl_assert(tab->mat->ctx,do { if (tab->n_con == bmap->n_eq + bmap->n_ineq) break ; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "tab->n_con == bmap->n_eq + bmap->n_ineq" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1877); return -1; } while (0); } while (0) | |||
1877 | tab->n_con == bmap->n_eq + bmap->n_ineq, return -1)do { if (tab->n_con == bmap->n_eq + bmap->n_ineq) break ; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "tab->n_con == bmap->n_eq + bmap->n_ineq" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1877); return -1; } while (0); } while (0); | |||
1878 | tab->bmap = isl_basic_map_add_ineq(tab->bmap, ineq); | |||
1879 | if (isl_tab_push(tab, isl_tab_undo_bmap_ineq) < 0) | |||
1880 | return -1; | |||
1881 | if (!tab->bmap) | |||
1882 | return -1; | |||
1883 | } | |||
1884 | if (tab->cone) { | |||
1885 | isl_int_init(cst)isl_sioimath_init((cst)); | |||
1886 | isl_int_set_si(cst, 0)isl_sioimath_set_si((cst), 0); | |||
1887 | isl_int_swap(ineq[0], cst)isl_sioimath_swap((ineq[0]), (cst)); | |||
1888 | } | |||
1889 | r = isl_tab_add_row(tab, ineq); | |||
1890 | if (tab->cone) { | |||
1891 | isl_int_swap(ineq[0], cst)isl_sioimath_swap((ineq[0]), (cst)); | |||
1892 | isl_int_clear(cst)isl_sioimath_clear((cst)); | |||
1893 | } | |||
1894 | if (r < 0) | |||
1895 | return -1; | |||
1896 | tab->con[r].is_nonneg = 1; | |||
1897 | if (isl_tab_push_var(tab, isl_tab_undo_nonneg, &tab->con[r]) < 0) | |||
1898 | return -1; | |||
1899 | if (isl_tab_row_is_redundant(tab, tab->con[r].index)) { | |||
1900 | if (isl_tab_mark_redundant(tab, tab->con[r].index) < 0) | |||
1901 | return -1; | |||
1902 | return 0; | |||
1903 | } | |||
1904 | ||||
1905 | sgn = restore_row(tab, &tab->con[r]); | |||
1906 | if (sgn < -1) | |||
1907 | return -1; | |||
1908 | if (sgn < 0) | |||
1909 | return isl_tab_mark_empty(tab); | |||
1910 | if (tab->con[r].is_row && isl_tab_row_is_redundant(tab, tab->con[r].index)) | |||
1911 | if (isl_tab_mark_redundant(tab, tab->con[r].index) < 0) | |||
1912 | return -1; | |||
1913 | return 0; | |||
1914 | } | |||
1915 | ||||
1916 | /* Pivot a non-negative variable down until it reaches the value zero | |||
1917 | * and then pivot the variable into a column position. | |||
1918 | */ | |||
1919 | static int to_col(struct isl_tab *tab, struct isl_tab_var *var) WARN_UNUSED__attribute__((__warn_unused_result__)); | |||
1920 | static int to_col(struct isl_tab *tab, struct isl_tab_var *var) | |||
1921 | { | |||
1922 | int i; | |||
1923 | int row, col; | |||
1924 | unsigned off = 2 + tab->M; | |||
1925 | ||||
1926 | if (!var->is_row) | |||
1927 | return 0; | |||
1928 | ||||
1929 | while (isl_int_is_pos(tab->mat->row[var->index][1])(isl_sioimath_sgn(*(tab->mat->row[var->index][1])) > 0)) { | |||
1930 | find_pivot(tab, var, NULL((void*)0), -1, &row, &col); | |||
1931 | isl_assert(tab->mat->ctx, row != -1, return -1)do { if (row != -1) break; do { isl_handle_error(tab->mat-> ctx, isl_error_unknown, "Assertion \"" "row != -1" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1931); return -1; } while (0); } while (0); | |||
1932 | if (isl_tab_pivot(tab, row, col) < 0) | |||
1933 | return -1; | |||
1934 | if (!var->is_row) | |||
1935 | return 0; | |||
1936 | } | |||
1937 | ||||
1938 | for (i = tab->n_dead; i < tab->n_col; ++i) | |||
1939 | if (!isl_int_is_zero(tab->mat->row[var->index][off + i])(isl_sioimath_sgn(*(tab->mat->row[var->index][off + i ])) == 0)) | |||
1940 | break; | |||
1941 | ||||
1942 | isl_assert(tab->mat->ctx, i < tab->n_col, return -1)do { if (i < tab->n_col) break; do { isl_handle_error(tab ->mat->ctx, isl_error_unknown, "Assertion \"" "i < tab->n_col" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1942); return -1; } while (0); } while (0); | |||
1943 | if (isl_tab_pivot(tab, var->index, i) < 0) | |||
1944 | return -1; | |||
1945 | ||||
1946 | return 0; | |||
1947 | } | |||
1948 | ||||
1949 | /* We assume Gaussian elimination has been performed on the equalities. | |||
1950 | * The equalities can therefore never conflict. | |||
1951 | * Adding the equalities is currently only really useful for a later call | |||
1952 | * to isl_tab_ineq_type. | |||
1953 | */ | |||
1954 | static struct isl_tab *add_eq(struct isl_tab *tab, isl_int *eq) | |||
1955 | { | |||
1956 | int i; | |||
1957 | int r; | |||
1958 | ||||
1959 | if (!tab) | |||
1960 | return NULL((void*)0); | |||
1961 | r = isl_tab_add_row(tab, eq); | |||
1962 | if (r < 0) | |||
1963 | goto error; | |||
1964 | ||||
1965 | r = tab->con[r].index; | |||
1966 | i = isl_seq_first_non_zero(tab->mat->row[r] + 2 + tab->M + tab->n_dead, | |||
1967 | tab->n_col - tab->n_dead); | |||
1968 | isl_assert(tab->mat->ctx, i >= 0, goto error)do { if (i >= 0) break; do { isl_handle_error(tab->mat-> ctx, isl_error_unknown, "Assertion \"" "i >= 0" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 1968); goto error; } while (0); } while (0); | |||
1969 | i += tab->n_dead; | |||
1970 | if (isl_tab_pivot(tab, r, i) < 0) | |||
1971 | goto error; | |||
1972 | if (isl_tab_kill_col(tab, i) < 0) | |||
1973 | goto error; | |||
1974 | tab->n_eq++; | |||
1975 | ||||
1976 | return tab; | |||
1977 | error: | |||
1978 | isl_tab_free(tab); | |||
1979 | return NULL((void*)0); | |||
1980 | } | |||
1981 | ||||
1982 | static int row_is_manifestly_zero(struct isl_tab *tab, int row) | |||
1983 | { | |||
1984 | unsigned off = 2 + tab->M; | |||
1985 | ||||
1986 | if (!isl_int_is_zero(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) == 0)) | |||
1987 | return 0; | |||
1988 | if (tab->M && !isl_int_is_zero(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) == 0)) | |||
1989 | return 0; | |||
1990 | return isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead, | |||
1991 | tab->n_col - tab->n_dead) == -1; | |||
1992 | } | |||
1993 | ||||
1994 | /* Add an equality that is known to be valid for the given tableau. | |||
1995 | */ | |||
1996 | int isl_tab_add_valid_eq(struct isl_tab *tab, isl_int *eq) | |||
1997 | { | |||
1998 | struct isl_tab_var *var; | |||
1999 | int r; | |||
2000 | ||||
2001 | if (!tab) | |||
2002 | return -1; | |||
2003 | r = isl_tab_add_row(tab, eq); | |||
2004 | if (r < 0) | |||
2005 | return -1; | |||
2006 | ||||
2007 | var = &tab->con[r]; | |||
2008 | r = var->index; | |||
2009 | if (row_is_manifestly_zero(tab, r)) { | |||
2010 | var->is_zero = 1; | |||
2011 | if (isl_tab_mark_redundant(tab, r) < 0) | |||
2012 | return -1; | |||
2013 | return 0; | |||
2014 | } | |||
2015 | ||||
2016 | if (isl_int_is_neg(tab->mat->row[r][1])(isl_sioimath_sgn(*(tab->mat->row[r][1])) < 0)) { | |||
2017 | isl_seq_neg(tab->mat->row[r] + 1, tab->mat->row[r] + 1, | |||
2018 | 1 + tab->n_col); | |||
2019 | var->negated = 1; | |||
2020 | } | |||
2021 | var->is_nonneg = 1; | |||
2022 | if (to_col(tab, var) < 0) | |||
2023 | return -1; | |||
2024 | var->is_nonneg = 0; | |||
2025 | if (isl_tab_kill_col(tab, var->index) < 0) | |||
2026 | return -1; | |||
2027 | ||||
2028 | return 0; | |||
2029 | } | |||
2030 | ||||
2031 | static int add_zero_row(struct isl_tab *tab) | |||
2032 | { | |||
2033 | int r; | |||
2034 | isl_int *row; | |||
2035 | ||||
2036 | r = isl_tab_allocate_con(tab); | |||
2037 | if (r < 0) | |||
2038 | return -1; | |||
2039 | ||||
2040 | row = tab->mat->row[tab->con[r].index]; | |||
2041 | isl_seq_clr(row + 1, 1 + tab->M + tab->n_col); | |||
2042 | isl_int_set_si(row[0], 1)isl_sioimath_set_si((row[0]), 1); | |||
2043 | ||||
2044 | return r; | |||
2045 | } | |||
2046 | ||||
2047 | /* Add equality "eq" and check if it conflicts with the | |||
2048 | * previously added constraints or if it is obviously redundant. | |||
2049 | */ | |||
2050 | int isl_tab_add_eq(struct isl_tab *tab, isl_int *eq) | |||
2051 | { | |||
2052 | struct isl_tab_undo *snap = NULL((void*)0); | |||
2053 | struct isl_tab_var *var; | |||
2054 | int r; | |||
2055 | int row; | |||
2056 | int sgn; | |||
2057 | isl_int cst; | |||
2058 | ||||
2059 | if (!tab) | |||
2060 | return -1; | |||
2061 | isl_assert(tab->mat->ctx, !tab->M, return -1)do { if (!tab->M) break; do { isl_handle_error(tab->mat ->ctx, isl_error_unknown, "Assertion \"" "!tab->M" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2061); return -1; } while (0); } while (0); | |||
2062 | ||||
2063 | if (tab->need_undo) | |||
2064 | snap = isl_tab_snap(tab); | |||
2065 | ||||
2066 | if (tab->cone) { | |||
2067 | isl_int_init(cst)isl_sioimath_init((cst)); | |||
2068 | isl_int_set_si(cst, 0)isl_sioimath_set_si((cst), 0); | |||
2069 | isl_int_swap(eq[0], cst)isl_sioimath_swap((eq[0]), (cst)); | |||
2070 | } | |||
2071 | r = isl_tab_add_row(tab, eq); | |||
2072 | if (tab->cone) { | |||
2073 | isl_int_swap(eq[0], cst)isl_sioimath_swap((eq[0]), (cst)); | |||
2074 | isl_int_clear(cst)isl_sioimath_clear((cst)); | |||
2075 | } | |||
2076 | if (r < 0) | |||
2077 | return -1; | |||
2078 | ||||
2079 | var = &tab->con[r]; | |||
2080 | row = var->index; | |||
2081 | if (row_is_manifestly_zero(tab, row)) { | |||
2082 | if (snap) | |||
2083 | return isl_tab_rollback(tab, snap); | |||
2084 | return drop_row(tab, row); | |||
2085 | } | |||
2086 | ||||
2087 | if (tab->bmap) { | |||
2088 | tab->bmap = isl_basic_map_add_ineq(tab->bmap, eq); | |||
2089 | if (isl_tab_push(tab, isl_tab_undo_bmap_ineq) < 0) | |||
2090 | return -1; | |||
2091 | isl_seq_neg(eq, eq, 1 + tab->n_var); | |||
2092 | tab->bmap = isl_basic_map_add_ineq(tab->bmap, eq); | |||
2093 | isl_seq_neg(eq, eq, 1 + tab->n_var); | |||
2094 | if (isl_tab_push(tab, isl_tab_undo_bmap_ineq) < 0) | |||
2095 | return -1; | |||
2096 | if (!tab->bmap) | |||
2097 | return -1; | |||
2098 | if (add_zero_row(tab) < 0) | |||
2099 | return -1; | |||
2100 | } | |||
2101 | ||||
2102 | sgn = isl_int_sgn(tab->mat->row[row][1])isl_sioimath_sgn(*(tab->mat->row[row][1])); | |||
2103 | ||||
2104 | if (sgn > 0) { | |||
2105 | isl_seq_neg(tab->mat->row[row] + 1, tab->mat->row[row] + 1, | |||
2106 | 1 + tab->n_col); | |||
2107 | var->negated = 1; | |||
2108 | sgn = -1; | |||
2109 | } | |||
2110 | ||||
2111 | if (sgn < 0) { | |||
2112 | sgn = sign_of_max(tab, var); | |||
2113 | if (sgn < -1) | |||
2114 | return -1; | |||
2115 | if (sgn < 0) { | |||
2116 | if (isl_tab_mark_empty(tab) < 0) | |||
2117 | return -1; | |||
2118 | return 0; | |||
2119 | } | |||
2120 | } | |||
2121 | ||||
2122 | var->is_nonneg = 1; | |||
2123 | if (to_col(tab, var) < 0) | |||
2124 | return -1; | |||
2125 | var->is_nonneg = 0; | |||
2126 | if (isl_tab_kill_col(tab, var->index) < 0) | |||
2127 | return -1; | |||
2128 | ||||
2129 | return 0; | |||
2130 | } | |||
2131 | ||||
2132 | /* Construct and return an inequality that expresses an upper bound | |||
2133 | * on the given div. | |||
2134 | * In particular, if the div is given by | |||
2135 | * | |||
2136 | * d = floor(e/m) | |||
2137 | * | |||
2138 | * then the inequality expresses | |||
2139 | * | |||
2140 | * m d <= e | |||
2141 | */ | |||
2142 | static struct isl_vec *ineq_for_div(struct isl_basic_map *bmap, unsigned div) | |||
2143 | { | |||
2144 | unsigned total; | |||
2145 | unsigned div_pos; | |||
2146 | struct isl_vec *ineq; | |||
2147 | ||||
2148 | if (!bmap) | |||
2149 | return NULL((void*)0); | |||
2150 | ||||
2151 | total = isl_basic_map_total_dim(bmap); | |||
2152 | div_pos = 1 + total - bmap->n_div + div; | |||
2153 | ||||
2154 | ineq = isl_vec_alloc(bmap->ctx, 1 + total); | |||
2155 | if (!ineq) | |||
2156 | return NULL((void*)0); | |||
2157 | ||||
2158 | isl_seq_cpy(ineq->el, bmap->div[div] + 1, 1 + total); | |||
2159 | isl_int_neg(ineq->el[div_pos], bmap->div[div][0])isl_sioimath_neg((ineq->el[div_pos]), *(bmap->div[div][ 0])); | |||
2160 | return ineq; | |||
2161 | } | |||
2162 | ||||
2163 | /* For a div d = floor(f/m), add the constraints | |||
2164 | * | |||
2165 | * f - m d >= 0 | |||
2166 | * -(f-(m-1)) + m d >= 0 | |||
2167 | * | |||
2168 | * Note that the second constraint is the negation of | |||
2169 | * | |||
2170 | * f - m d >= m | |||
2171 | * | |||
2172 | * If add_ineq is not NULL, then this function is used | |||
2173 | * instead of isl_tab_add_ineq to effectively add the inequalities. | |||
2174 | */ | |||
2175 | static int add_div_constraints(struct isl_tab *tab, unsigned div, | |||
2176 | int (*add_ineq)(void *user, isl_int *), void *user) | |||
2177 | { | |||
2178 | unsigned total; | |||
2179 | unsigned div_pos; | |||
2180 | struct isl_vec *ineq; | |||
2181 | ||||
2182 | total = isl_basic_map_total_dim(tab->bmap); | |||
2183 | div_pos = 1 + total - tab->bmap->n_div + div; | |||
2184 | ||||
2185 | ineq = ineq_for_div(tab->bmap, div); | |||
2186 | if (!ineq) | |||
2187 | goto error; | |||
2188 | ||||
2189 | if (add_ineq) { | |||
2190 | if (add_ineq(user, ineq->el) < 0) | |||
2191 | goto error; | |||
2192 | } else { | |||
2193 | if (isl_tab_add_ineq(tab, ineq->el) < 0) | |||
2194 | goto error; | |||
2195 | } | |||
2196 | ||||
2197 | isl_seq_neg(ineq->el, tab->bmap->div[div] + 1, 1 + total); | |||
2198 | isl_int_set(ineq->el[div_pos], tab->bmap->div[div][0])isl_sioimath_set((ineq->el[div_pos]), *(tab->bmap->div [div][0])); | |||
2199 | isl_int_add(ineq->el[0], ineq->el[0], ineq->el[div_pos])isl_sioimath_add((ineq->el[0]), *(ineq->el[0]), *(ineq-> el[div_pos])); | |||
2200 | isl_int_sub_ui(ineq->el[0], ineq->el[0], 1)isl_sioimath_sub_ui((ineq->el[0]), *(ineq->el[0]), 1); | |||
2201 | ||||
2202 | if (add_ineq) { | |||
2203 | if (add_ineq(user, ineq->el) < 0) | |||
2204 | goto error; | |||
2205 | } else { | |||
2206 | if (isl_tab_add_ineq(tab, ineq->el) < 0) | |||
2207 | goto error; | |||
2208 | } | |||
2209 | ||||
2210 | isl_vec_free(ineq); | |||
2211 | ||||
2212 | return 0; | |||
2213 | error: | |||
2214 | isl_vec_free(ineq); | |||
2215 | return -1; | |||
2216 | } | |||
2217 | ||||
2218 | /* Check whether the div described by "div" is obviously non-negative. | |||
2219 | * If we are using a big parameter, then we will encode the div | |||
2220 | * as div' = M + div, which is always non-negative. | |||
2221 | * Otherwise, we check whether div is a non-negative affine combination | |||
2222 | * of non-negative variables. | |||
2223 | */ | |||
2224 | static int div_is_nonneg(struct isl_tab *tab, __isl_keep isl_vec *div) | |||
2225 | { | |||
2226 | int i; | |||
2227 | ||||
2228 | if (tab->M) | |||
2229 | return 1; | |||
2230 | ||||
2231 | if (isl_int_is_neg(div->el[1])(isl_sioimath_sgn(*(div->el[1])) < 0)) | |||
2232 | return 0; | |||
2233 | ||||
2234 | for (i = 0; i < tab->n_var; ++i) { | |||
2235 | if (isl_int_is_neg(div->el[2 + i])(isl_sioimath_sgn(*(div->el[2 + i])) < 0)) | |||
2236 | return 0; | |||
2237 | if (isl_int_is_zero(div->el[2 + i])(isl_sioimath_sgn(*(div->el[2 + i])) == 0)) | |||
2238 | continue; | |||
2239 | if (!tab->var[i].is_nonneg) | |||
2240 | return 0; | |||
2241 | } | |||
2242 | ||||
2243 | return 1; | |||
2244 | } | |||
2245 | ||||
2246 | /* Add an extra div, prescribed by "div" to the tableau and | |||
2247 | * the associated bmap (which is assumed to be non-NULL). | |||
2248 | * | |||
2249 | * If add_ineq is not NULL, then this function is used instead | |||
2250 | * of isl_tab_add_ineq to add the div constraints. | |||
2251 | * This complication is needed because the code in isl_tab_pip | |||
2252 | * wants to perform some extra processing when an inequality | |||
2253 | * is added to the tableau. | |||
2254 | */ | |||
2255 | int isl_tab_add_div(struct isl_tab *tab, __isl_keep isl_vec *div, | |||
2256 | int (*add_ineq)(void *user, isl_int *), void *user) | |||
2257 | { | |||
2258 | int r; | |||
2259 | int k; | |||
2260 | int nonneg; | |||
2261 | ||||
2262 | if (!tab || !div) | |||
2263 | return -1; | |||
2264 | ||||
2265 | isl_assert(tab->mat->ctx, tab->bmap, return -1)do { if (tab->bmap) break; do { isl_handle_error(tab->mat ->ctx, isl_error_unknown, "Assertion \"" "tab->bmap" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2265); return -1; } while (0); } while (0); | |||
2266 | ||||
2267 | nonneg = div_is_nonneg(tab, div); | |||
2268 | ||||
2269 | if (isl_tab_extend_cons(tab, 3) < 0) | |||
2270 | return -1; | |||
2271 | if (isl_tab_extend_vars(tab, 1) < 0) | |||
2272 | return -1; | |||
2273 | r = isl_tab_allocate_var(tab); | |||
2274 | if (r < 0) | |||
2275 | return -1; | |||
2276 | ||||
2277 | if (nonneg) | |||
2278 | tab->var[r].is_nonneg = 1; | |||
2279 | ||||
2280 | tab->bmap = isl_basic_map_extend_space(tab->bmap, | |||
2281 | isl_basic_map_get_space(tab->bmap), 1, 0, 2); | |||
2282 | k = isl_basic_map_alloc_div(tab->bmap); | |||
2283 | if (k < 0) | |||
2284 | return -1; | |||
2285 | isl_seq_cpy(tab->bmap->div[k], div->el, div->size); | |||
2286 | if (isl_tab_push(tab, isl_tab_undo_bmap_div) < 0) | |||
2287 | return -1; | |||
2288 | ||||
2289 | if (add_div_constraints(tab, k, add_ineq, user) < 0) | |||
2290 | return -1; | |||
2291 | ||||
2292 | return r; | |||
2293 | } | |||
2294 | ||||
2295 | /* If "track" is set, then we want to keep track of all constraints in tab | |||
2296 | * in its bmap field. This field is initialized from a copy of "bmap", | |||
2297 | * so we need to make sure that all constraints in "bmap" also appear | |||
2298 | * in the constructed tab. | |||
2299 | */ | |||
2300 | __isl_give struct isl_tab *isl_tab_from_basic_map( | |||
2301 | __isl_keep isl_basic_map *bmap, int track) | |||
2302 | { | |||
2303 | int i; | |||
2304 | struct isl_tab *tab; | |||
2305 | ||||
2306 | if (!bmap) | |||
2307 | return NULL((void*)0); | |||
2308 | tab = isl_tab_alloc(bmap->ctx, | |||
2309 | isl_basic_map_total_dim(bmap) + bmap->n_ineq + 1, | |||
2310 | isl_basic_map_total_dim(bmap), 0); | |||
2311 | if (!tab) | |||
2312 | return NULL((void*)0); | |||
2313 | tab->preserve = track; | |||
2314 | tab->rational = ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)(!!(((bmap)->flags) & ((1 << 4)))); | |||
2315 | if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY)(!!(((bmap)->flags) & ((1 << 1))))) { | |||
2316 | if (isl_tab_mark_empty(tab) < 0) | |||
2317 | goto error; | |||
2318 | goto done; | |||
2319 | } | |||
2320 | for (i = 0; i < bmap->n_eq; ++i) { | |||
2321 | tab = add_eq(tab, bmap->eq[i]); | |||
2322 | if (!tab) | |||
2323 | return tab; | |||
2324 | } | |||
2325 | for (i = 0; i < bmap->n_ineq; ++i) { | |||
2326 | if (isl_tab_add_ineq(tab, bmap->ineq[i]) < 0) | |||
2327 | goto error; | |||
2328 | if (tab->empty) | |||
2329 | goto done; | |||
2330 | } | |||
2331 | done: | |||
2332 | if (track && isl_tab_track_bmap(tab, isl_basic_map_copy(bmap)) < 0) | |||
2333 | goto error; | |||
2334 | return tab; | |||
2335 | error: | |||
2336 | isl_tab_free(tab); | |||
2337 | return NULL((void*)0); | |||
2338 | } | |||
2339 | ||||
2340 | __isl_give struct isl_tab *isl_tab_from_basic_set( | |||
2341 | __isl_keep isl_basic_setisl_basic_map *bset, int track) | |||
2342 | { | |||
2343 | return isl_tab_from_basic_map(bset, track); | |||
2344 | } | |||
2345 | ||||
2346 | /* Construct a tableau corresponding to the recession cone of "bset". | |||
2347 | */ | |||
2348 | struct isl_tab *isl_tab_from_recession_cone(__isl_keep isl_basic_setisl_basic_map *bset, | |||
2349 | int parametric) | |||
2350 | { | |||
2351 | isl_int cst; | |||
2352 | int i; | |||
2353 | struct isl_tab *tab; | |||
2354 | unsigned offset = 0; | |||
2355 | ||||
2356 | if (!bset) | |||
2357 | return NULL((void*)0); | |||
2358 | if (parametric) | |||
2359 | offset = isl_basic_set_dim(bset, isl_dim_param); | |||
2360 | tab = isl_tab_alloc(bset->ctx, bset->n_eq + bset->n_ineq, | |||
2361 | isl_basic_set_total_dim(bset) - offset, 0); | |||
2362 | if (!tab) | |||
2363 | return NULL((void*)0); | |||
2364 | tab->rational = ISL_F_ISSET(bset, ISL_BASIC_SET_RATIONAL)(!!(((bset)->flags) & ((1 << 4)))); | |||
2365 | tab->cone = 1; | |||
2366 | ||||
2367 | isl_int_init(cst)isl_sioimath_init((cst)); | |||
2368 | isl_int_set_si(cst, 0)isl_sioimath_set_si((cst), 0); | |||
2369 | for (i = 0; i < bset->n_eq; ++i) { | |||
2370 | isl_int_swap(bset->eq[i][offset], cst)isl_sioimath_swap((bset->eq[i][offset]), (cst)); | |||
2371 | if (offset > 0) { | |||
2372 | if (isl_tab_add_eq(tab, bset->eq[i] + offset) < 0) | |||
2373 | goto error; | |||
2374 | } else | |||
2375 | tab = add_eq(tab, bset->eq[i]); | |||
2376 | isl_int_swap(bset->eq[i][offset], cst)isl_sioimath_swap((bset->eq[i][offset]), (cst)); | |||
2377 | if (!tab) | |||
2378 | goto done; | |||
2379 | } | |||
2380 | for (i = 0; i < bset->n_ineq; ++i) { | |||
2381 | int r; | |||
2382 | isl_int_swap(bset->ineq[i][offset], cst)isl_sioimath_swap((bset->ineq[i][offset]), (cst)); | |||
2383 | r = isl_tab_add_row(tab, bset->ineq[i] + offset); | |||
2384 | isl_int_swap(bset->ineq[i][offset], cst)isl_sioimath_swap((bset->ineq[i][offset]), (cst)); | |||
2385 | if (r < 0) | |||
2386 | goto error; | |||
2387 | tab->con[r].is_nonneg = 1; | |||
2388 | if (isl_tab_push_var(tab, isl_tab_undo_nonneg, &tab->con[r]) < 0) | |||
2389 | goto error; | |||
2390 | } | |||
2391 | done: | |||
2392 | isl_int_clear(cst)isl_sioimath_clear((cst)); | |||
2393 | return tab; | |||
2394 | error: | |||
2395 | isl_int_clear(cst)isl_sioimath_clear((cst)); | |||
2396 | isl_tab_free(tab); | |||
2397 | return NULL((void*)0); | |||
2398 | } | |||
2399 | ||||
2400 | /* Assuming "tab" is the tableau of a cone, check if the cone is | |||
2401 | * bounded, i.e., if it is empty or only contains the origin. | |||
2402 | */ | |||
2403 | int isl_tab_cone_is_bounded(struct isl_tab *tab) | |||
2404 | { | |||
2405 | int i; | |||
2406 | ||||
2407 | if (!tab) | |||
2408 | return -1; | |||
2409 | if (tab->empty) | |||
2410 | return 1; | |||
2411 | if (tab->n_dead == tab->n_col) | |||
2412 | return 1; | |||
2413 | ||||
2414 | for (;;) { | |||
2415 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
2416 | struct isl_tab_var *var; | |||
2417 | int sgn; | |||
2418 | var = isl_tab_var_from_row(tab, i); | |||
2419 | if (!var->is_nonneg) | |||
2420 | continue; | |||
2421 | sgn = sign_of_max(tab, var); | |||
2422 | if (sgn < -1) | |||
2423 | return -1; | |||
2424 | if (sgn != 0) | |||
2425 | return 0; | |||
2426 | if (close_row(tab, var) < 0) | |||
2427 | return -1; | |||
2428 | break; | |||
2429 | } | |||
2430 | if (tab->n_dead == tab->n_col) | |||
2431 | return 1; | |||
2432 | if (i == tab->n_row) | |||
2433 | return 0; | |||
2434 | } | |||
2435 | } | |||
2436 | ||||
2437 | int isl_tab_sample_is_integer(struct isl_tab *tab) | |||
2438 | { | |||
2439 | int i; | |||
2440 | ||||
2441 | if (!tab) | |||
2442 | return -1; | |||
2443 | ||||
2444 | for (i = 0; i < tab->n_var; ++i) { | |||
2445 | int row; | |||
2446 | if (!tab->var[i].is_row) | |||
2447 | continue; | |||
2448 | row = tab->var[i].index; | |||
2449 | if (!isl_int_is_divisible_by(tab->mat->row[row][1],isl_sioimath_is_divisible_by(*(tab->mat->row[row][1]), * (tab->mat->row[row][0])) | |||
2450 | tab->mat->row[row][0])isl_sioimath_is_divisible_by(*(tab->mat->row[row][1]), * (tab->mat->row[row][0]))) | |||
2451 | return 0; | |||
2452 | } | |||
2453 | return 1; | |||
2454 | } | |||
2455 | ||||
2456 | static struct isl_vec *extract_integer_sample(struct isl_tab *tab) | |||
2457 | { | |||
2458 | int i; | |||
2459 | struct isl_vec *vec; | |||
2460 | ||||
2461 | vec = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_var); | |||
2462 | if (!vec) | |||
2463 | return NULL((void*)0); | |||
2464 | ||||
2465 | isl_int_set_si(vec->block.data[0], 1)isl_sioimath_set_si((vec->block.data[0]), 1); | |||
2466 | for (i = 0; i < tab->n_var; ++i) { | |||
2467 | if (!tab->var[i].is_row) | |||
2468 | isl_int_set_si(vec->block.data[1 + i], 0)isl_sioimath_set_si((vec->block.data[1 + i]), 0); | |||
2469 | else { | |||
2470 | int row = tab->var[i].index; | |||
2471 | isl_int_divexact(vec->block.data[1 + i],isl_sioimath_tdiv_q((vec->block.data[1 + i]), *(tab->mat ->row[row][1]), *(tab->mat->row[row][0])) | |||
2472 | tab->mat->row[row][1], tab->mat->row[row][0])isl_sioimath_tdiv_q((vec->block.data[1 + i]), *(tab->mat ->row[row][1]), *(tab->mat->row[row][0])); | |||
2473 | } | |||
2474 | } | |||
2475 | ||||
2476 | return vec; | |||
2477 | } | |||
2478 | ||||
2479 | struct isl_vec *isl_tab_get_sample_value(struct isl_tab *tab) | |||
2480 | { | |||
2481 | int i; | |||
2482 | struct isl_vec *vec; | |||
2483 | isl_int m; | |||
2484 | ||||
2485 | if (!tab) | |||
2486 | return NULL((void*)0); | |||
2487 | ||||
2488 | vec = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_var); | |||
2489 | if (!vec) | |||
2490 | return NULL((void*)0); | |||
2491 | ||||
2492 | isl_int_init(m)isl_sioimath_init((m)); | |||
2493 | ||||
2494 | isl_int_set_si(vec->block.data[0], 1)isl_sioimath_set_si((vec->block.data[0]), 1); | |||
2495 | for (i = 0; i < tab->n_var; ++i) { | |||
2496 | int row; | |||
2497 | if (!tab->var[i].is_row) { | |||
2498 | isl_int_set_si(vec->block.data[1 + i], 0)isl_sioimath_set_si((vec->block.data[1 + i]), 0); | |||
2499 | continue; | |||
2500 | } | |||
2501 | row = tab->var[i].index; | |||
2502 | isl_int_gcd(m, vec->block.data[0], tab->mat->row[row][0])isl_sioimath_gcd((m), *(vec->block.data[0]), *(tab->mat ->row[row][0])); | |||
2503 | isl_int_divexact(m, tab->mat->row[row][0], m)isl_sioimath_tdiv_q((m), *(tab->mat->row[row][0]), *(m) ); | |||
2504 | isl_seq_scale(vec->block.data, vec->block.data, m, 1 + i); | |||
2505 | isl_int_divexact(m, vec->block.data[0], tab->mat->row[row][0])isl_sioimath_tdiv_q((m), *(vec->block.data[0]), *(tab-> mat->row[row][0])); | |||
2506 | isl_int_mul(vec->block.data[1 + i], m, tab->mat->row[row][1])isl_sioimath_mul((vec->block.data[1 + i]), *(m), *(tab-> mat->row[row][1])); | |||
2507 | } | |||
2508 | vec = isl_vec_normalize(vec); | |||
2509 | ||||
2510 | isl_int_clear(m)isl_sioimath_clear((m)); | |||
2511 | return vec; | |||
2512 | } | |||
2513 | ||||
2514 | /* Update "bmap" based on the results of the tableau "tab". | |||
2515 | * In particular, implicit equalities are made explicit, redundant constraints | |||
2516 | * are removed and if the sample value happens to be integer, it is stored | |||
2517 | * in "bmap" (unless "bmap" already had an integer sample). | |||
2518 | * | |||
2519 | * The tableau is assumed to have been created from "bmap" using | |||
2520 | * isl_tab_from_basic_map. | |||
2521 | */ | |||
2522 | struct isl_basic_map *isl_basic_map_update_from_tab(struct isl_basic_map *bmap, | |||
2523 | struct isl_tab *tab) | |||
2524 | { | |||
2525 | int i; | |||
2526 | unsigned n_eq; | |||
2527 | ||||
2528 | if (!bmap) | |||
2529 | return NULL((void*)0); | |||
2530 | if (!tab) | |||
2531 | return bmap; | |||
2532 | ||||
2533 | n_eq = tab->n_eq; | |||
2534 | if (tab->empty) | |||
2535 | bmap = isl_basic_map_set_to_empty(bmap); | |||
2536 | else | |||
2537 | for (i = bmap->n_ineq - 1; i >= 0; --i) { | |||
2538 | if (isl_tab_is_equality(tab, n_eq + i)) | |||
2539 | isl_basic_map_inequality_to_equality(bmap, i); | |||
2540 | else if (isl_tab_is_redundant(tab, n_eq + i)) | |||
2541 | isl_basic_map_drop_inequality(bmap, i); | |||
2542 | } | |||
2543 | if (bmap->n_eq != n_eq) | |||
2544 | isl_basic_map_gauss(bmap, NULL((void*)0)); | |||
2545 | if (!tab->rational && | |||
2546 | !bmap->sample && isl_tab_sample_is_integer(tab)) | |||
2547 | bmap->sample = extract_integer_sample(tab); | |||
2548 | return bmap; | |||
2549 | } | |||
2550 | ||||
2551 | struct isl_basic_setisl_basic_map *isl_basic_set_update_from_tab(struct isl_basic_setisl_basic_map *bset, | |||
2552 | struct isl_tab *tab) | |||
2553 | { | |||
2554 | return (struct isl_basic_setisl_basic_map *)isl_basic_map_update_from_tab( | |||
2555 | (struct isl_basic_map *)bset, tab); | |||
2556 | } | |||
2557 | ||||
2558 | /* Given a non-negative variable "var", add a new non-negative variable | |||
2559 | * that is the opposite of "var", ensuring that var can only attain the | |||
2560 | * value zero. | |||
2561 | * If var = n/d is a row variable, then the new variable = -n/d. | |||
2562 | * If var is a column variables, then the new variable = -var. | |||
2563 | * If the new variable cannot attain non-negative values, then | |||
2564 | * the resulting tableau is empty. | |||
2565 | * Otherwise, we know the value will be zero and we close the row. | |||
2566 | */ | |||
2567 | static int cut_to_hyperplane(struct isl_tab *tab, struct isl_tab_var *var) | |||
2568 | { | |||
2569 | unsigned r; | |||
2570 | isl_int *row; | |||
2571 | int sgn; | |||
2572 | unsigned off = 2 + tab->M; | |||
2573 | ||||
2574 | if (var->is_zero) | |||
2575 | return 0; | |||
2576 | isl_assert(tab->mat->ctx, !var->is_redundant, return -1)do { if (!var->is_redundant) break; do { isl_handle_error( tab->mat->ctx, isl_error_unknown, "Assertion \"" "!var->is_redundant" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2576); return -1; } while (0); } while (0); | |||
2577 | isl_assert(tab->mat->ctx, var->is_nonneg, return -1)do { if (var->is_nonneg) break; do { isl_handle_error(tab-> mat->ctx, isl_error_unknown, "Assertion \"" "var->is_nonneg" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2577); return -1; } while (0); } while (0); | |||
2578 | ||||
2579 | if (isl_tab_extend_cons(tab, 1) < 0) | |||
2580 | return -1; | |||
2581 | ||||
2582 | r = tab->n_con; | |||
2583 | tab->con[r].index = tab->n_row; | |||
2584 | tab->con[r].is_row = 1; | |||
2585 | tab->con[r].is_nonneg = 0; | |||
2586 | tab->con[r].is_zero = 0; | |||
2587 | tab->con[r].is_redundant = 0; | |||
2588 | tab->con[r].frozen = 0; | |||
2589 | tab->con[r].negated = 0; | |||
2590 | tab->row_var[tab->n_row] = ~r; | |||
2591 | row = tab->mat->row[tab->n_row]; | |||
2592 | ||||
2593 | if (var->is_row) { | |||
2594 | isl_int_set(row[0], tab->mat->row[var->index][0])isl_sioimath_set((row[0]), *(tab->mat->row[var->index ][0])); | |||
2595 | isl_seq_neg(row + 1, | |||
2596 | tab->mat->row[var->index] + 1, 1 + tab->n_col); | |||
2597 | } else { | |||
2598 | isl_int_set_si(row[0], 1)isl_sioimath_set_si((row[0]), 1); | |||
2599 | isl_seq_clr(row + 1, 1 + tab->n_col); | |||
2600 | isl_int_set_si(row[off + var->index], -1)isl_sioimath_set_si((row[off + var->index]), -1); | |||
2601 | } | |||
2602 | ||||
2603 | tab->n_row++; | |||
2604 | tab->n_con++; | |||
2605 | if (isl_tab_push_var(tab, isl_tab_undo_allocate, &tab->con[r]) < 0) | |||
2606 | return -1; | |||
2607 | ||||
2608 | sgn = sign_of_max(tab, &tab->con[r]); | |||
2609 | if (sgn < -1) | |||
2610 | return -1; | |||
2611 | if (sgn < 0) { | |||
2612 | if (isl_tab_mark_empty(tab) < 0) | |||
2613 | return -1; | |||
2614 | return 0; | |||
2615 | } | |||
2616 | tab->con[r].is_nonneg = 1; | |||
2617 | if (isl_tab_push_var(tab, isl_tab_undo_nonneg, &tab->con[r]) < 0) | |||
2618 | return -1; | |||
2619 | /* sgn == 0 */ | |||
2620 | if (close_row(tab, &tab->con[r]) < 0) | |||
2621 | return -1; | |||
2622 | ||||
2623 | return 0; | |||
2624 | } | |||
2625 | ||||
2626 | /* Given a tableau "tab" and an inequality constraint "con" of the tableau, | |||
2627 | * relax the inequality by one. That is, the inequality r >= 0 is replaced | |||
2628 | * by r' = r + 1 >= 0. | |||
2629 | * If r is a row variable, we simply increase the constant term by one | |||
2630 | * (taking into account the denominator). | |||
2631 | * If r is a column variable, then we need to modify each row that | |||
2632 | * refers to r = r' - 1 by substituting this equality, effectively | |||
2633 | * subtracting the coefficient of the column from the constant. | |||
2634 | * We should only do this if the minimum is manifestly unbounded, | |||
2635 | * however. Otherwise, we may end up with negative sample values | |||
2636 | * for non-negative variables. | |||
2637 | * So, if r is a column variable with a minimum that is not | |||
2638 | * manifestly unbounded, then we need to move it to a row. | |||
2639 | * However, the sample value of this row may be negative, | |||
2640 | * even after the relaxation, so we need to restore it. | |||
2641 | * We therefore prefer to pivot a column up to a row, if possible. | |||
2642 | */ | |||
2643 | int isl_tab_relax(struct isl_tab *tab, int con) | |||
2644 | { | |||
2645 | struct isl_tab_var *var; | |||
2646 | ||||
2647 | if (!tab) | |||
2648 | return -1; | |||
2649 | ||||
2650 | var = &tab->con[con]; | |||
2651 | ||||
2652 | if (var->is_row && (var->index < 0 || var->index < tab->n_redundant)) | |||
2653 | isl_die(tab->mat->ctx, isl_error_invalid,do { isl_handle_error(tab->mat->ctx, isl_error_invalid, "cannot relax redundant constraint", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2654); return -1; } while (0) | |||
2654 | "cannot relax redundant constraint", return -1)do { isl_handle_error(tab->mat->ctx, isl_error_invalid, "cannot relax redundant constraint", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2654); return -1; } while (0); | |||
2655 | if (!var->is_row && (var->index < 0 || var->index < tab->n_dead)) | |||
2656 | isl_die(tab->mat->ctx, isl_error_invalid,do { isl_handle_error(tab->mat->ctx, isl_error_invalid, "cannot relax dead constraint", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2657); return -1; } while (0) | |||
2657 | "cannot relax dead constraint", return -1)do { isl_handle_error(tab->mat->ctx, isl_error_invalid, "cannot relax dead constraint", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2657); return -1; } while (0); | |||
2658 | ||||
2659 | if (!var->is_row && !max_is_manifestly_unbounded(tab, var)) | |||
2660 | if (to_row(tab, var, 1) < 0) | |||
2661 | return -1; | |||
2662 | if (!var->is_row && !min_is_manifestly_unbounded(tab, var)) | |||
2663 | if (to_row(tab, var, -1) < 0) | |||
2664 | return -1; | |||
2665 | ||||
2666 | if (var->is_row) { | |||
2667 | isl_int_add(tab->mat->row[var->index][1],isl_sioimath_add((tab->mat->row[var->index][1]), *(tab ->mat->row[var->index][1]), *(tab->mat->row[var ->index][0])) | |||
2668 | tab->mat->row[var->index][1], tab->mat->row[var->index][0])isl_sioimath_add((tab->mat->row[var->index][1]), *(tab ->mat->row[var->index][1]), *(tab->mat->row[var ->index][0])); | |||
2669 | if (restore_row(tab, var) < 0) | |||
2670 | return -1; | |||
2671 | } else { | |||
2672 | int i; | |||
2673 | unsigned off = 2 + tab->M; | |||
2674 | ||||
2675 | for (i = 0; i < tab->n_row; ++i) { | |||
2676 | if (isl_int_is_zero(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index ])) == 0)) | |||
2677 | continue; | |||
2678 | isl_int_sub(tab->mat->row[i][1], tab->mat->row[i][1],isl_sioimath_sub((tab->mat->row[i][1]), *(tab->mat-> row[i][1]), *(tab->mat->row[i][off + var->index])) | |||
2679 | tab->mat->row[i][off + var->index])isl_sioimath_sub((tab->mat->row[i][1]), *(tab->mat-> row[i][1]), *(tab->mat->row[i][off + var->index])); | |||
2680 | } | |||
2681 | ||||
2682 | } | |||
2683 | ||||
2684 | if (isl_tab_push_var(tab, isl_tab_undo_relax, var) < 0) | |||
2685 | return -1; | |||
2686 | ||||
2687 | return 0; | |||
2688 | } | |||
2689 | ||||
2690 | /* Replace the variable v at position "pos" in the tableau "tab" | |||
2691 | * by v' = v + shift. | |||
2692 | * | |||
2693 | * If the variable is in a column, then we first check if we can | |||
2694 | * simply plug in v = v' - shift. The effect on a row with | |||
2695 | * coefficient f/d for variable v is that the constant term c/d | |||
2696 | * is replaced by (c - f * shift)/d. If shift is positive and | |||
2697 | * f is negative for each row that needs to remain non-negative, | |||
2698 | * then this is clearly safe. In other words, if the minimum of v | |||
2699 | * is manifestly unbounded, then we can keep v in a column position. | |||
2700 | * Otherwise, we can pivot it down to a row. | |||
2701 | * Similarly, if shift is negative, we need to check if the maximum | |||
2702 | * of is manifestly unbounded. | |||
2703 | * | |||
2704 | * If the variable is in a row (from the start or after pivoting), | |||
2705 | * then the constant term c/d is replaced by (c + d * shift)/d. | |||
2706 | */ | |||
2707 | int isl_tab_shift_var(struct isl_tab *tab, int pos, isl_int shift) | |||
2708 | { | |||
2709 | struct isl_tab_var *var; | |||
2710 | ||||
2711 | if (!tab) | |||
2712 | return -1; | |||
2713 | if (isl_int_is_zero(shift)(isl_sioimath_sgn(*(shift)) == 0)) | |||
2714 | return 0; | |||
2715 | ||||
2716 | var = &tab->var[pos]; | |||
2717 | if (!var->is_row) { | |||
2718 | if (isl_int_is_neg(shift)(isl_sioimath_sgn(*(shift)) < 0)) { | |||
2719 | if (!max_is_manifestly_unbounded(tab, var)) | |||
2720 | if (to_row(tab, var, 1) < 0) | |||
2721 | return -1; | |||
2722 | } else { | |||
2723 | if (!min_is_manifestly_unbounded(tab, var)) | |||
2724 | if (to_row(tab, var, -1) < 0) | |||
2725 | return -1; | |||
2726 | } | |||
2727 | } | |||
2728 | ||||
2729 | if (var->is_row) { | |||
2730 | isl_int_addmul(tab->mat->row[var->index][1],isl_sioimath_addmul((tab->mat->row[var->index][1]), * (shift), *(tab->mat->row[var->index][0])) | |||
2731 | shift, tab->mat->row[var->index][0])isl_sioimath_addmul((tab->mat->row[var->index][1]), * (shift), *(tab->mat->row[var->index][0])); | |||
2732 | } else { | |||
2733 | int i; | |||
2734 | unsigned off = 2 + tab->M; | |||
2735 | ||||
2736 | for (i = 0; i < tab->n_row; ++i) { | |||
2737 | if (isl_int_is_zero(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index ])) == 0)) | |||
2738 | continue; | |||
2739 | isl_int_submul(tab->mat->row[i][1],isl_sioimath_submul((tab->mat->row[i][1]), *(shift), *( tab->mat->row[i][off + var->index])) | |||
2740 | shift, tab->mat->row[i][off + var->index])isl_sioimath_submul((tab->mat->row[i][1]), *(shift), *( tab->mat->row[i][off + var->index])); | |||
2741 | } | |||
2742 | ||||
2743 | } | |||
2744 | ||||
2745 | return 0; | |||
2746 | } | |||
2747 | ||||
2748 | /* Remove the sign constraint from constraint "con". | |||
2749 | * | |||
2750 | * If the constraint variable was originally marked non-negative, | |||
2751 | * then we make sure we mark it non-negative again during rollback. | |||
2752 | */ | |||
2753 | int isl_tab_unrestrict(struct isl_tab *tab, int con) | |||
2754 | { | |||
2755 | struct isl_tab_var *var; | |||
2756 | ||||
2757 | if (!tab) | |||
2758 | return -1; | |||
2759 | ||||
2760 | var = &tab->con[con]; | |||
2761 | if (!var->is_nonneg) | |||
2762 | return 0; | |||
2763 | ||||
2764 | var->is_nonneg = 0; | |||
2765 | if (isl_tab_push_var(tab, isl_tab_undo_unrestrict, var) < 0) | |||
2766 | return -1; | |||
2767 | ||||
2768 | return 0; | |||
2769 | } | |||
2770 | ||||
2771 | int isl_tab_select_facet(struct isl_tab *tab, int con) | |||
2772 | { | |||
2773 | if (!tab) | |||
2774 | return -1; | |||
2775 | ||||
2776 | return cut_to_hyperplane(tab, &tab->con[con]); | |||
2777 | } | |||
2778 | ||||
2779 | static int may_be_equality(struct isl_tab *tab, int row) | |||
2780 | { | |||
2781 | return tab->rational ? isl_int_is_zero(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) == 0) | |||
2782 | : isl_int_lt(tab->mat->row[row][1],(isl_sioimath_cmp(*(tab->mat->row[row][1]), *(tab->mat ->row[row][0])) < 0) | |||
2783 | tab->mat->row[row][0])(isl_sioimath_cmp(*(tab->mat->row[row][1]), *(tab->mat ->row[row][0])) < 0); | |||
2784 | } | |||
2785 | ||||
2786 | /* Check for (near) equalities among the constraints. | |||
2787 | * A constraint is an equality if it is non-negative and if | |||
2788 | * its maximal value is either | |||
2789 | * - zero (in case of rational tableaus), or | |||
2790 | * - strictly less than 1 (in case of integer tableaus) | |||
2791 | * | |||
2792 | * We first mark all non-redundant and non-dead variables that | |||
2793 | * are not frozen and not obviously not an equality. | |||
2794 | * Then we iterate over all marked variables if they can attain | |||
2795 | * any values larger than zero or at least one. | |||
2796 | * If the maximal value is zero, we mark any column variables | |||
2797 | * that appear in the row as being zero and mark the row as being redundant. | |||
2798 | * Otherwise, if the maximal value is strictly less than one (and the | |||
2799 | * tableau is integer), then we restrict the value to being zero | |||
2800 | * by adding an opposite non-negative variable. | |||
2801 | */ | |||
2802 | int isl_tab_detect_implicit_equalities(struct isl_tab *tab) | |||
2803 | { | |||
2804 | int i; | |||
2805 | unsigned n_marked; | |||
2806 | ||||
2807 | if (!tab) | |||
2808 | return -1; | |||
2809 | if (tab->empty) | |||
2810 | return 0; | |||
2811 | if (tab->n_dead == tab->n_col) | |||
2812 | return 0; | |||
2813 | ||||
2814 | n_marked = 0; | |||
2815 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
2816 | struct isl_tab_var *var = isl_tab_var_from_row(tab, i); | |||
2817 | var->marked = !var->frozen && var->is_nonneg && | |||
2818 | may_be_equality(tab, i); | |||
2819 | if (var->marked) | |||
2820 | n_marked++; | |||
2821 | } | |||
2822 | for (i = tab->n_dead; i < tab->n_col; ++i) { | |||
2823 | struct isl_tab_var *var = var_from_col(tab, i); | |||
2824 | var->marked = !var->frozen && var->is_nonneg; | |||
2825 | if (var->marked) | |||
2826 | n_marked++; | |||
2827 | } | |||
2828 | while (n_marked) { | |||
2829 | struct isl_tab_var *var; | |||
2830 | int sgn; | |||
2831 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
2832 | var = isl_tab_var_from_row(tab, i); | |||
2833 | if (var->marked) | |||
2834 | break; | |||
2835 | } | |||
2836 | if (i == tab->n_row) { | |||
2837 | for (i = tab->n_dead; i < tab->n_col; ++i) { | |||
2838 | var = var_from_col(tab, i); | |||
2839 | if (var->marked) | |||
2840 | break; | |||
2841 | } | |||
2842 | if (i == tab->n_col) | |||
2843 | break; | |||
2844 | } | |||
2845 | var->marked = 0; | |||
2846 | n_marked--; | |||
2847 | sgn = sign_of_max(tab, var); | |||
2848 | if (sgn < 0) | |||
2849 | return -1; | |||
2850 | if (sgn == 0) { | |||
2851 | if (close_row(tab, var) < 0) | |||
2852 | return -1; | |||
2853 | } else if (!tab->rational && !at_least_one(tab, var)) { | |||
2854 | if (cut_to_hyperplane(tab, var) < 0) | |||
2855 | return -1; | |||
2856 | return isl_tab_detect_implicit_equalities(tab); | |||
2857 | } | |||
2858 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
2859 | var = isl_tab_var_from_row(tab, i); | |||
2860 | if (!var->marked) | |||
2861 | continue; | |||
2862 | if (may_be_equality(tab, i)) | |||
2863 | continue; | |||
2864 | var->marked = 0; | |||
2865 | n_marked--; | |||
2866 | } | |||
2867 | } | |||
2868 | ||||
2869 | return 0; | |||
2870 | } | |||
2871 | ||||
2872 | /* Update the element of row_var or col_var that corresponds to | |||
2873 | * constraint tab->con[i] to a move from position "old" to position "i". | |||
2874 | */ | |||
2875 | static int update_con_after_move(struct isl_tab *tab, int i, int old) | |||
2876 | { | |||
2877 | int *p; | |||
2878 | int index; | |||
2879 | ||||
2880 | index = tab->con[i].index; | |||
2881 | if (index == -1) | |||
2882 | return 0; | |||
2883 | p = tab->con[i].is_row ? tab->row_var : tab->col_var; | |||
2884 | if (p[index] != ~old) | |||
2885 | isl_die(tab->mat->ctx, isl_error_internal,do { isl_handle_error(tab->mat->ctx, isl_error_internal , "broken internal state", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2886); return -1; } while (0) | |||
2886 | "broken internal state", return -1)do { isl_handle_error(tab->mat->ctx, isl_error_internal , "broken internal state", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 2886); return -1; } while (0); | |||
2887 | p[index] = ~i; | |||
2888 | ||||
2889 | return 0; | |||
2890 | } | |||
2891 | ||||
2892 | /* Rotate the "n" constraints starting at "first" to the right, | |||
2893 | * putting the last constraint in the position of the first constraint. | |||
2894 | */ | |||
2895 | static int rotate_constraints(struct isl_tab *tab, int first, int n) | |||
2896 | { | |||
2897 | int i, last; | |||
2898 | struct isl_tab_var var; | |||
2899 | ||||
2900 | if (n <= 1) | |||
2901 | return 0; | |||
2902 | ||||
2903 | last = first + n - 1; | |||
2904 | var = tab->con[last]; | |||
2905 | for (i = last; i > first; --i) { | |||
2906 | tab->con[i] = tab->con[i - 1]; | |||
2907 | if (update_con_after_move(tab, i, i - 1) < 0) | |||
2908 | return -1; | |||
2909 | } | |||
2910 | tab->con[first] = var; | |||
2911 | if (update_con_after_move(tab, first, last) < 0) | |||
2912 | return -1; | |||
2913 | ||||
2914 | return 0; | |||
2915 | } | |||
2916 | ||||
2917 | /* Make the equalities that are implicit in "bmap" but that have been | |||
2918 | * detected in the corresponding "tab" explicit in "bmap" and update | |||
2919 | * "tab" to reflect the new order of the constraints. | |||
2920 | * | |||
2921 | * In particular, if inequality i is an implicit equality then | |||
2922 | * isl_basic_map_inequality_to_equality will move the inequality | |||
2923 | * in front of the other equality and it will move the last inequality | |||
2924 | * in the position of inequality i. | |||
2925 | * In the tableau, the inequalities of "bmap" are stored after the equalities | |||
2926 | * and so the original order | |||
2927 | * | |||
2928 | * E E E E E A A A I B B B B L | |||
2929 | * | |||
2930 | * is changed into | |||
2931 | * | |||
2932 | * I E E E E E A A A L B B B B | |||
2933 | * | |||
2934 | * where I is the implicit equality, the E are equalities, | |||
2935 | * the A inequalities before I, the B inequalities after I and | |||
2936 | * L the last inequality. | |||
2937 | * We therefore need to rotate to the right two sets of constraints, | |||
2938 | * those up to and including I and those after I. | |||
2939 | * | |||
2940 | * If "tab" contains any constraints that are not in "bmap" then they | |||
2941 | * appear after those in "bmap" and they should be left untouched. | |||
2942 | * | |||
2943 | * Note that this function leaves "bmap" in a temporary state | |||
2944 | * as it does not call isl_basic_map_gauss. Calling this function | |||
2945 | * is the responsibility of the caller. | |||
2946 | */ | |||
2947 | __isl_give isl_basic_map *isl_tab_make_equalities_explicit(struct isl_tab *tab, | |||
2948 | __isl_take isl_basic_map *bmap) | |||
2949 | { | |||
2950 | int i; | |||
2951 | ||||
2952 | if (!tab || !bmap) | |||
2953 | return isl_basic_map_free(bmap); | |||
2954 | if (tab->empty) | |||
2955 | return bmap; | |||
2956 | ||||
2957 | for (i = bmap->n_ineq - 1; i >= 0; --i) { | |||
2958 | if (!isl_tab_is_equality(tab, bmap->n_eq + i)) | |||
2959 | continue; | |||
2960 | isl_basic_map_inequality_to_equality(bmap, i); | |||
2961 | if (rotate_constraints(tab, 0, tab->n_eq + i + 1) < 0) | |||
2962 | return isl_basic_map_free(bmap); | |||
2963 | if (rotate_constraints(tab, tab->n_eq + i + 1, | |||
2964 | bmap->n_ineq - i) < 0) | |||
2965 | return isl_basic_map_free(bmap); | |||
2966 | tab->n_eq++; | |||
2967 | } | |||
2968 | ||||
2969 | return bmap; | |||
2970 | } | |||
2971 | ||||
2972 | static int con_is_redundant(struct isl_tab *tab, struct isl_tab_var *var) | |||
2973 | { | |||
2974 | if (!tab) | |||
2975 | return -1; | |||
2976 | if (tab->rational) { | |||
2977 | int sgn = sign_of_min(tab, var); | |||
2978 | if (sgn < -1) | |||
2979 | return -1; | |||
2980 | return sgn >= 0; | |||
2981 | } else { | |||
2982 | int irred = isl_tab_min_at_most_neg_one(tab, var); | |||
2983 | if (irred < 0) | |||
2984 | return -1; | |||
2985 | return !irred; | |||
2986 | } | |||
2987 | } | |||
2988 | ||||
2989 | /* Check for (near) redundant constraints. | |||
2990 | * A constraint is redundant if it is non-negative and if | |||
2991 | * its minimal value (temporarily ignoring the non-negativity) is either | |||
2992 | * - zero (in case of rational tableaus), or | |||
2993 | * - strictly larger than -1 (in case of integer tableaus) | |||
2994 | * | |||
2995 | * We first mark all non-redundant and non-dead variables that | |||
2996 | * are not frozen and not obviously negatively unbounded. | |||
2997 | * Then we iterate over all marked variables if they can attain | |||
2998 | * any values smaller than zero or at most negative one. | |||
2999 | * If not, we mark the row as being redundant (assuming it hasn't | |||
3000 | * been detected as being obviously redundant in the mean time). | |||
3001 | */ | |||
3002 | int isl_tab_detect_redundant(struct isl_tab *tab) | |||
3003 | { | |||
3004 | int i; | |||
3005 | unsigned n_marked; | |||
3006 | ||||
3007 | if (!tab) | |||
| ||||
3008 | return -1; | |||
3009 | if (tab->empty) | |||
3010 | return 0; | |||
3011 | if (tab->n_redundant == tab->n_row) | |||
3012 | return 0; | |||
3013 | ||||
3014 | n_marked = 0; | |||
3015 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
3016 | struct isl_tab_var *var = isl_tab_var_from_row(tab, i); | |||
3017 | var->marked = !var->frozen && var->is_nonneg; | |||
3018 | if (var->marked) | |||
3019 | n_marked++; | |||
3020 | } | |||
3021 | for (i = tab->n_dead; i < tab->n_col; ++i) { | |||
3022 | struct isl_tab_var *var = var_from_col(tab, i); | |||
3023 | var->marked = !var->frozen && var->is_nonneg && | |||
3024 | !min_is_manifestly_unbounded(tab, var); | |||
3025 | if (var->marked) | |||
3026 | n_marked++; | |||
3027 | } | |||
3028 | while (n_marked) { | |||
3029 | struct isl_tab_var *var; | |||
3030 | int red; | |||
3031 | for (i = tab->n_redundant; i < tab->n_row; ++i) { | |||
3032 | var = isl_tab_var_from_row(tab, i); | |||
3033 | if (var->marked) | |||
3034 | break; | |||
3035 | } | |||
3036 | if (i == tab->n_row) { | |||
3037 | for (i = tab->n_dead; i < tab->n_col; ++i) { | |||
3038 | var = var_from_col(tab, i); | |||
3039 | if (var->marked) | |||
3040 | break; | |||
3041 | } | |||
3042 | if (i == tab->n_col) | |||
3043 | break; | |||
3044 | } | |||
3045 | var->marked = 0; | |||
| ||||
3046 | n_marked--; | |||
3047 | red = con_is_redundant(tab, var); | |||
3048 | if (red < 0) | |||
3049 | return -1; | |||
3050 | if (red && !var->is_redundant) | |||
3051 | if (isl_tab_mark_redundant(tab, var->index) < 0) | |||
3052 | return -1; | |||
3053 | for (i = tab->n_dead; i < tab->n_col; ++i) { | |||
3054 | var = var_from_col(tab, i); | |||
3055 | if (!var->marked) | |||
3056 | continue; | |||
3057 | if (!min_is_manifestly_unbounded(tab, var)) | |||
3058 | continue; | |||
3059 | var->marked = 0; | |||
3060 | n_marked--; | |||
3061 | } | |||
3062 | } | |||
3063 | ||||
3064 | return 0; | |||
3065 | } | |||
3066 | ||||
3067 | int isl_tab_is_equality(struct isl_tab *tab, int con) | |||
3068 | { | |||
3069 | int row; | |||
3070 | unsigned off; | |||
3071 | ||||
3072 | if (!tab) | |||
3073 | return -1; | |||
3074 | if (tab->con[con].is_zero) | |||
3075 | return 1; | |||
3076 | if (tab->con[con].is_redundant) | |||
3077 | return 0; | |||
3078 | if (!tab->con[con].is_row) | |||
3079 | return tab->con[con].index < tab->n_dead; | |||
3080 | ||||
3081 | row = tab->con[con].index; | |||
3082 | ||||
3083 | off = 2 + tab->M; | |||
3084 | return isl_int_is_zero(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) == 0) && | |||
3085 | (!tab->M || isl_int_is_zero(tab->mat->row[row][2])(isl_sioimath_sgn(*(tab->mat->row[row][2])) == 0)) && | |||
3086 | isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead, | |||
3087 | tab->n_col - tab->n_dead) == -1; | |||
3088 | } | |||
3089 | ||||
3090 | /* Return the minimal value of the affine expression "f" with denominator | |||
3091 | * "denom" in *opt, *opt_denom, assuming the tableau is not empty and | |||
3092 | * the expression cannot attain arbitrarily small values. | |||
3093 | * If opt_denom is NULL, then *opt is rounded up to the nearest integer. | |||
3094 | * The return value reflects the nature of the result (empty, unbounded, | |||
3095 | * minimal value returned in *opt). | |||
3096 | */ | |||
3097 | enum isl_lp_result isl_tab_min(struct isl_tab *tab, | |||
3098 | isl_int *f, isl_int denom, isl_int *opt, isl_int *opt_denom, | |||
3099 | unsigned flags) | |||
3100 | { | |||
3101 | int r; | |||
3102 | enum isl_lp_result res = isl_lp_ok; | |||
3103 | struct isl_tab_var *var; | |||
3104 | struct isl_tab_undo *snap; | |||
3105 | ||||
3106 | if (!tab) | |||
3107 | return isl_lp_error; | |||
3108 | ||||
3109 | if (tab->empty) | |||
3110 | return isl_lp_empty; | |||
3111 | ||||
3112 | snap = isl_tab_snap(tab); | |||
3113 | r = isl_tab_add_row(tab, f); | |||
3114 | if (r < 0) | |||
3115 | return isl_lp_error; | |||
3116 | var = &tab->con[r]; | |||
3117 | for (;;) { | |||
3118 | int row, col; | |||
3119 | find_pivot(tab, var, var, -1, &row, &col); | |||
3120 | if (row == var->index) { | |||
3121 | res = isl_lp_unbounded; | |||
3122 | break; | |||
3123 | } | |||
3124 | if (row == -1) | |||
3125 | break; | |||
3126 | if (isl_tab_pivot(tab, row, col) < 0) | |||
3127 | return isl_lp_error; | |||
3128 | } | |||
3129 | isl_int_mul(tab->mat->row[var->index][0],isl_sioimath_mul((tab->mat->row[var->index][0]), *(tab ->mat->row[var->index][0]), *(denom)) | |||
3130 | tab->mat->row[var->index][0], denom)isl_sioimath_mul((tab->mat->row[var->index][0]), *(tab ->mat->row[var->index][0]), *(denom)); | |||
3131 | if (ISL_FL_ISSET(flags, ISL_TAB_SAVE_DUAL)(!!((flags) & ((1 << 0))))) { | |||
3132 | int i; | |||
3133 | ||||
3134 | isl_vec_free(tab->dual); | |||
3135 | tab->dual = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_con); | |||
3136 | if (!tab->dual) | |||
3137 | return isl_lp_error; | |||
3138 | isl_int_set(tab->dual->el[0], tab->mat->row[var->index][0])isl_sioimath_set((tab->dual->el[0]), *(tab->mat-> row[var->index][0])); | |||
3139 | for (i = 0; i < tab->n_con; ++i) { | |||
3140 | int pos; | |||
3141 | if (tab->con[i].is_row) { | |||
3142 | isl_int_set_si(tab->dual->el[1 + i], 0)isl_sioimath_set_si((tab->dual->el[1 + i]), 0); | |||
3143 | continue; | |||
3144 | } | |||
3145 | pos = 2 + tab->M + tab->con[i].index; | |||
3146 | if (tab->con[i].negated) | |||
3147 | isl_int_neg(tab->dual->el[1 + i],isl_sioimath_neg((tab->dual->el[1 + i]), *(tab->mat-> row[var->index][pos])) | |||
3148 | tab->mat->row[var->index][pos])isl_sioimath_neg((tab->dual->el[1 + i]), *(tab->mat-> row[var->index][pos])); | |||
3149 | else | |||
3150 | isl_int_set(tab->dual->el[1 + i],isl_sioimath_set((tab->dual->el[1 + i]), *(tab->mat-> row[var->index][pos])) | |||
3151 | tab->mat->row[var->index][pos])isl_sioimath_set((tab->dual->el[1 + i]), *(tab->mat-> row[var->index][pos])); | |||
3152 | } | |||
3153 | } | |||
3154 | if (opt && res == isl_lp_ok) { | |||
3155 | if (opt_denom) { | |||
3156 | isl_int_set(*opt, tab->mat->row[var->index][1])isl_sioimath_set((*opt), *(tab->mat->row[var->index] [1])); | |||
3157 | isl_int_set(*opt_denom, tab->mat->row[var->index][0])isl_sioimath_set((*opt_denom), *(tab->mat->row[var-> index][0])); | |||
3158 | } else | |||
3159 | isl_int_cdiv_q(*opt, tab->mat->row[var->index][1],isl_sioimath_cdiv_q((*opt), *(tab->mat->row[var->index ][1]), *(tab->mat->row[var->index][0])) | |||
3160 | tab->mat->row[var->index][0])isl_sioimath_cdiv_q((*opt), *(tab->mat->row[var->index ][1]), *(tab->mat->row[var->index][0])); | |||
3161 | } | |||
3162 | if (isl_tab_rollback(tab, snap) < 0) | |||
3163 | return isl_lp_error; | |||
3164 | return res; | |||
3165 | } | |||
3166 | ||||
3167 | /* Is the constraint at position "con" marked as being redundant? | |||
3168 | * If it is marked as representing an equality, then it is not | |||
3169 | * considered to be redundant. | |||
3170 | * Note that isl_tab_mark_redundant marks both the isl_tab_var as | |||
3171 | * redundant and moves the corresponding row into the first | |||
3172 | * tab->n_redundant positions (or removes the row, assigning it index -1), | |||
3173 | * so the final test is actually redundant itself. | |||
3174 | */ | |||
3175 | int isl_tab_is_redundant(struct isl_tab *tab, int con) | |||
3176 | { | |||
3177 | if (!tab) | |||
3178 | return -1; | |||
3179 | if (con < 0 || con >= tab->n_con) | |||
3180 | isl_die(isl_tab_get_ctx(tab), isl_error_invalid,do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid , "position out of bounds", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3181); return -1; } while (0) | |||
3181 | "position out of bounds", return -1)do { isl_handle_error(isl_tab_get_ctx(tab), isl_error_invalid , "position out of bounds", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3181); return -1; } while (0); | |||
3182 | if (tab->con[con].is_zero) | |||
3183 | return 0; | |||
3184 | if (tab->con[con].is_redundant) | |||
3185 | return 1; | |||
3186 | return tab->con[con].is_row && tab->con[con].index < tab->n_redundant; | |||
3187 | } | |||
3188 | ||||
3189 | /* Take a snapshot of the tableau that can be restored by s call to | |||
3190 | * isl_tab_rollback. | |||
3191 | */ | |||
3192 | struct isl_tab_undo *isl_tab_snap(struct isl_tab *tab) | |||
3193 | { | |||
3194 | if (!tab) | |||
3195 | return NULL((void*)0); | |||
3196 | tab->need_undo = 1; | |||
3197 | return tab->top; | |||
3198 | } | |||
3199 | ||||
3200 | /* Undo the operation performed by isl_tab_relax. | |||
3201 | */ | |||
3202 | static int unrelax(struct isl_tab *tab, struct isl_tab_var *var) WARN_UNUSED__attribute__((__warn_unused_result__)); | |||
3203 | static int unrelax(struct isl_tab *tab, struct isl_tab_var *var) | |||
3204 | { | |||
3205 | unsigned off = 2 + tab->M; | |||
3206 | ||||
3207 | if (!var->is_row && !max_is_manifestly_unbounded(tab, var)) | |||
3208 | if (to_row(tab, var, 1) < 0) | |||
3209 | return -1; | |||
3210 | ||||
3211 | if (var->is_row) { | |||
3212 | isl_int_sub(tab->mat->row[var->index][1],isl_sioimath_sub((tab->mat->row[var->index][1]), *(tab ->mat->row[var->index][1]), *(tab->mat->row[var ->index][0])) | |||
3213 | tab->mat->row[var->index][1], tab->mat->row[var->index][0])isl_sioimath_sub((tab->mat->row[var->index][1]), *(tab ->mat->row[var->index][1]), *(tab->mat->row[var ->index][0])); | |||
3214 | if (var->is_nonneg) { | |||
3215 | int sgn = restore_row(tab, var); | |||
3216 | isl_assert(tab->mat->ctx, sgn >= 0, return -1)do { if (sgn >= 0) break; do { isl_handle_error(tab->mat ->ctx, isl_error_unknown, "Assertion \"" "sgn >= 0" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3216); return -1; } while (0); } while (0); | |||
3217 | } | |||
3218 | } else { | |||
3219 | int i; | |||
3220 | ||||
3221 | for (i = 0; i < tab->n_row; ++i) { | |||
3222 | if (isl_int_is_zero(tab->mat->row[i][off + var->index])(isl_sioimath_sgn(*(tab->mat->row[i][off + var->index ])) == 0)) | |||
3223 | continue; | |||
3224 | isl_int_add(tab->mat->row[i][1], tab->mat->row[i][1],isl_sioimath_add((tab->mat->row[i][1]), *(tab->mat-> row[i][1]), *(tab->mat->row[i][off + var->index])) | |||
3225 | tab->mat->row[i][off + var->index])isl_sioimath_add((tab->mat->row[i][1]), *(tab->mat-> row[i][1]), *(tab->mat->row[i][off + var->index])); | |||
3226 | } | |||
3227 | ||||
3228 | } | |||
3229 | ||||
3230 | return 0; | |||
3231 | } | |||
3232 | ||||
3233 | /* Undo the operation performed by isl_tab_unrestrict. | |||
3234 | * | |||
3235 | * In particular, mark the variable as being non-negative and make | |||
3236 | * sure the sample value respects this constraint. | |||
3237 | */ | |||
3238 | static int ununrestrict(struct isl_tab *tab, struct isl_tab_var *var) | |||
3239 | { | |||
3240 | var->is_nonneg = 1; | |||
3241 | ||||
3242 | if (var->is_row && restore_row(tab, var) < -1) | |||
3243 | return -1; | |||
3244 | ||||
3245 | return 0; | |||
3246 | } | |||
3247 | ||||
3248 | static int perform_undo_var(struct isl_tab *tab, struct isl_tab_undo *undo) WARN_UNUSED__attribute__((__warn_unused_result__)); | |||
3249 | static int perform_undo_var(struct isl_tab *tab, struct isl_tab_undo *undo) | |||
3250 | { | |||
3251 | struct isl_tab_var *var = var_from_index(tab, undo->u.var_index); | |||
3252 | switch (undo->type) { | |||
3253 | case isl_tab_undo_nonneg: | |||
3254 | var->is_nonneg = 0; | |||
3255 | break; | |||
3256 | case isl_tab_undo_redundant: | |||
3257 | var->is_redundant = 0; | |||
3258 | tab->n_redundant--; | |||
3259 | restore_row(tab, isl_tab_var_from_row(tab, tab->n_redundant)); | |||
3260 | break; | |||
3261 | case isl_tab_undo_freeze: | |||
3262 | var->frozen = 0; | |||
3263 | break; | |||
3264 | case isl_tab_undo_zero: | |||
3265 | var->is_zero = 0; | |||
3266 | if (!var->is_row) | |||
3267 | tab->n_dead--; | |||
3268 | break; | |||
3269 | case isl_tab_undo_allocate: | |||
3270 | if (undo->u.var_index >= 0) { | |||
3271 | isl_assert(tab->mat->ctx, !var->is_row, return -1)do { if (!var->is_row) break; do { isl_handle_error(tab-> mat->ctx, isl_error_unknown, "Assertion \"" "!var->is_row" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3271); return -1; } while (0); } while (0); | |||
3272 | return drop_col(tab, var->index); | |||
3273 | } | |||
3274 | if (!var->is_row) { | |||
3275 | if (!max_is_manifestly_unbounded(tab, var)) { | |||
3276 | if (to_row(tab, var, 1) < 0) | |||
3277 | return -1; | |||
3278 | } else if (!min_is_manifestly_unbounded(tab, var)) { | |||
3279 | if (to_row(tab, var, -1) < 0) | |||
3280 | return -1; | |||
3281 | } else | |||
3282 | if (to_row(tab, var, 0) < 0) | |||
3283 | return -1; | |||
3284 | } | |||
3285 | return drop_row(tab, var->index); | |||
3286 | case isl_tab_undo_relax: | |||
3287 | return unrelax(tab, var); | |||
3288 | case isl_tab_undo_unrestrict: | |||
3289 | return ununrestrict(tab, var); | |||
3290 | default: | |||
3291 | isl_die(tab->mat->ctx, isl_error_internal,do { isl_handle_error(tab->mat->ctx, isl_error_internal , "perform_undo_var called on invalid undo record", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3293); return -1; } while (0) | |||
3292 | "perform_undo_var called on invalid undo record",do { isl_handle_error(tab->mat->ctx, isl_error_internal , "perform_undo_var called on invalid undo record", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3293); return -1; } while (0) | |||
3293 | return -1)do { isl_handle_error(tab->mat->ctx, isl_error_internal , "perform_undo_var called on invalid undo record", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3293); return -1; } while (0); | |||
3294 | } | |||
3295 | ||||
3296 | return 0; | |||
3297 | } | |||
3298 | ||||
3299 | /* Restore the tableau to the state where the basic variables | |||
3300 | * are those in "col_var". | |||
3301 | * We first construct a list of variables that are currently in | |||
3302 | * the basis, but shouldn't. Then we iterate over all variables | |||
3303 | * that should be in the basis and for each one that is currently | |||
3304 | * not in the basis, we exchange it with one of the elements of the | |||
3305 | * list constructed before. | |||
3306 | * We can always find an appropriate variable to pivot with because | |||
3307 | * the current basis is mapped to the old basis by a non-singular | |||
3308 | * matrix and so we can never end up with a zero row. | |||
3309 | */ | |||
3310 | static int restore_basis(struct isl_tab *tab, int *col_var) | |||
3311 | { | |||
3312 | int i, j; | |||
3313 | int n_extra = 0; | |||
3314 | int *extra = NULL((void*)0); /* current columns that contain bad stuff */ | |||
3315 | unsigned off = 2 + tab->M; | |||
3316 | ||||
3317 | extra = isl_alloc_array(tab->mat->ctx, int, tab->n_col)((int *)isl_malloc_or_die(tab->mat->ctx, (tab->n_col )*sizeof(int))); | |||
3318 | if (tab->n_col && !extra) | |||
3319 | goto error; | |||
3320 | for (i = 0; i < tab->n_col; ++i) { | |||
3321 | for (j = 0; j < tab->n_col; ++j) | |||
3322 | if (tab->col_var[i] == col_var[j]) | |||
3323 | break; | |||
3324 | if (j < tab->n_col) | |||
3325 | continue; | |||
3326 | extra[n_extra++] = i; | |||
3327 | } | |||
3328 | for (i = 0; i < tab->n_col && n_extra > 0; ++i) { | |||
3329 | struct isl_tab_var *var; | |||
3330 | int row; | |||
3331 | ||||
3332 | for (j = 0; j < tab->n_col; ++j) | |||
3333 | if (col_var[i] == tab->col_var[j]) | |||
3334 | break; | |||
3335 | if (j < tab->n_col) | |||
3336 | continue; | |||
3337 | var = var_from_index(tab, col_var[i]); | |||
3338 | row = var->index; | |||
3339 | for (j = 0; j < n_extra; ++j) | |||
3340 | if (!isl_int_is_zero(tab->mat->row[row][off+extra[j]])(isl_sioimath_sgn(*(tab->mat->row[row][off+extra[j]])) == 0)) | |||
3341 | break; | |||
3342 | isl_assert(tab->mat->ctx, j < n_extra, goto error)do { if (j < n_extra) break; do { isl_handle_error(tab-> mat->ctx, isl_error_unknown, "Assertion \"" "j < n_extra" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3342); goto error; } while (0); } while (0); | |||
3343 | if (isl_tab_pivot(tab, row, extra[j]) < 0) | |||
3344 | goto error; | |||
3345 | extra[j] = extra[--n_extra]; | |||
3346 | } | |||
3347 | ||||
3348 | free(extra); | |||
3349 | return 0; | |||
3350 | error: | |||
3351 | free(extra); | |||
3352 | return -1; | |||
3353 | } | |||
3354 | ||||
3355 | /* Remove all samples with index n or greater, i.e., those samples | |||
3356 | * that were added since we saved this number of samples in | |||
3357 | * isl_tab_save_samples. | |||
3358 | */ | |||
3359 | static void drop_samples_since(struct isl_tab *tab, int n) | |||
3360 | { | |||
3361 | int i; | |||
3362 | ||||
3363 | for (i = tab->n_sample - 1; i >= 0 && tab->n_sample > n; --i) { | |||
3364 | if (tab->sample_index[i] < n) | |||
3365 | continue; | |||
3366 | ||||
3367 | if (i != tab->n_sample - 1) { | |||
3368 | int t = tab->sample_index[tab->n_sample-1]; | |||
3369 | tab->sample_index[tab->n_sample-1] = tab->sample_index[i]; | |||
3370 | tab->sample_index[i] = t; | |||
3371 | isl_mat_swap_rows(tab->samples, tab->n_sample-1, i); | |||
3372 | } | |||
3373 | tab->n_sample--; | |||
3374 | } | |||
3375 | } | |||
3376 | ||||
3377 | static int perform_undo(struct isl_tab *tab, struct isl_tab_undo *undo) WARN_UNUSED__attribute__((__warn_unused_result__)); | |||
3378 | static int perform_undo(struct isl_tab *tab, struct isl_tab_undo *undo) | |||
3379 | { | |||
3380 | switch (undo->type) { | |||
3381 | case isl_tab_undo_rational: | |||
3382 | tab->rational = 0; | |||
3383 | break; | |||
3384 | case isl_tab_undo_empty: | |||
3385 | tab->empty = 0; | |||
3386 | break; | |||
3387 | case isl_tab_undo_nonneg: | |||
3388 | case isl_tab_undo_redundant: | |||
3389 | case isl_tab_undo_freeze: | |||
3390 | case isl_tab_undo_zero: | |||
3391 | case isl_tab_undo_allocate: | |||
3392 | case isl_tab_undo_relax: | |||
3393 | case isl_tab_undo_unrestrict: | |||
3394 | return perform_undo_var(tab, undo); | |||
3395 | case isl_tab_undo_bmap_eq: | |||
3396 | return isl_basic_map_free_equality(tab->bmap, 1); | |||
3397 | case isl_tab_undo_bmap_ineq: | |||
3398 | return isl_basic_map_free_inequality(tab->bmap, 1); | |||
3399 | case isl_tab_undo_bmap_div: | |||
3400 | if (isl_basic_map_free_div(tab->bmap, 1) < 0) | |||
3401 | return -1; | |||
3402 | if (tab->samples) | |||
3403 | tab->samples->n_col--; | |||
3404 | break; | |||
3405 | case isl_tab_undo_saved_basis: | |||
3406 | if (restore_basis(tab, undo->u.col_var) < 0) | |||
3407 | return -1; | |||
3408 | break; | |||
3409 | case isl_tab_undo_drop_sample: | |||
3410 | tab->n_outside--; | |||
3411 | break; | |||
3412 | case isl_tab_undo_saved_samples: | |||
3413 | drop_samples_since(tab, undo->u.n); | |||
3414 | break; | |||
3415 | case isl_tab_undo_callback: | |||
3416 | return undo->u.callback->run(undo->u.callback); | |||
3417 | default: | |||
3418 | isl_assert(tab->mat->ctx, 0, return -1)do { if (0) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown, "Assertion \"" "0" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3418); return -1; } while (0); } while (0); | |||
3419 | } | |||
3420 | return 0; | |||
3421 | } | |||
3422 | ||||
3423 | /* Return the tableau to the state it was in when the snapshot "snap" | |||
3424 | * was taken. | |||
3425 | */ | |||
3426 | int isl_tab_rollback(struct isl_tab *tab, struct isl_tab_undo *snap) | |||
3427 | { | |||
3428 | struct isl_tab_undo *undo, *next; | |||
3429 | ||||
3430 | if (!tab) | |||
3431 | return -1; | |||
3432 | ||||
3433 | tab->in_undo = 1; | |||
3434 | for (undo = tab->top; undo && undo != &tab->bottom; undo = next) { | |||
3435 | next = undo->next; | |||
3436 | if (undo == snap) | |||
3437 | break; | |||
3438 | if (perform_undo(tab, undo) < 0) { | |||
3439 | tab->top = undo; | |||
3440 | free_undo(tab); | |||
3441 | tab->in_undo = 0; | |||
3442 | return -1; | |||
3443 | } | |||
3444 | free_undo_record(undo); | |||
3445 | } | |||
3446 | tab->in_undo = 0; | |||
3447 | tab->top = undo; | |||
3448 | if (!undo) | |||
3449 | return -1; | |||
3450 | return 0; | |||
3451 | } | |||
3452 | ||||
3453 | /* The given row "row" represents an inequality violated by all | |||
3454 | * points in the tableau. Check for some special cases of such | |||
3455 | * separating constraints. | |||
3456 | * In particular, if the row has been reduced to the constant -1, | |||
3457 | * then we know the inequality is adjacent (but opposite) to | |||
3458 | * an equality in the tableau. | |||
3459 | * If the row has been reduced to r = c*(-1 -r'), with r' an inequality | |||
3460 | * of the tableau and c a positive constant, then the inequality | |||
3461 | * is adjacent (but opposite) to the inequality r'. | |||
3462 | */ | |||
3463 | static enum isl_ineq_type separation_type(struct isl_tab *tab, unsigned row) | |||
3464 | { | |||
3465 | int pos; | |||
3466 | unsigned off = 2 + tab->M; | |||
3467 | ||||
3468 | if (tab->rational) | |||
3469 | return isl_ineq_separate; | |||
3470 | ||||
3471 | if (!isl_int_is_one(tab->mat->row[row][0])(isl_sioimath_cmp_si(*(tab->mat->row[row][0]), 1) == 0)) | |||
3472 | return isl_ineq_separate; | |||
3473 | ||||
3474 | pos = isl_seq_first_non_zero(tab->mat->row[row] + off + tab->n_dead, | |||
3475 | tab->n_col - tab->n_dead); | |||
3476 | if (pos == -1) { | |||
3477 | if (isl_int_is_negone(tab->mat->row[row][1])(isl_sioimath_cmp_si(*(tab->mat->row[row][1]), -1) == 0 )) | |||
3478 | return isl_ineq_adj_eq; | |||
3479 | else | |||
3480 | return isl_ineq_separate; | |||
3481 | } | |||
3482 | ||||
3483 | if (!isl_int_eq(tab->mat->row[row][1],(isl_sioimath_cmp(*(tab->mat->row[row][1]), *(tab->mat ->row[row][off + tab->n_dead + pos])) == 0) | |||
3484 | tab->mat->row[row][off + tab->n_dead + pos])(isl_sioimath_cmp(*(tab->mat->row[row][1]), *(tab->mat ->row[row][off + tab->n_dead + pos])) == 0)) | |||
3485 | return isl_ineq_separate; | |||
3486 | ||||
3487 | pos = isl_seq_first_non_zero( | |||
3488 | tab->mat->row[row] + off + tab->n_dead + pos + 1, | |||
3489 | tab->n_col - tab->n_dead - pos - 1); | |||
3490 | ||||
3491 | return pos == -1 ? isl_ineq_adj_ineq : isl_ineq_separate; | |||
3492 | } | |||
3493 | ||||
3494 | /* Check the effect of inequality "ineq" on the tableau "tab". | |||
3495 | * The result may be | |||
3496 | * isl_ineq_redundant: satisfied by all points in the tableau | |||
3497 | * isl_ineq_separate: satisfied by no point in the tableau | |||
3498 | * isl_ineq_cut: satisfied by some by not all points | |||
3499 | * isl_ineq_adj_eq: adjacent to an equality | |||
3500 | * isl_ineq_adj_ineq: adjacent to an inequality. | |||
3501 | */ | |||
3502 | enum isl_ineq_type isl_tab_ineq_type(struct isl_tab *tab, isl_int *ineq) | |||
3503 | { | |||
3504 | enum isl_ineq_type type = isl_ineq_error; | |||
3505 | struct isl_tab_undo *snap = NULL((void*)0); | |||
3506 | int con; | |||
3507 | int row; | |||
3508 | ||||
3509 | if (!tab) | |||
3510 | return isl_ineq_error; | |||
3511 | ||||
3512 | if (isl_tab_extend_cons(tab, 1) < 0) | |||
3513 | return isl_ineq_error; | |||
3514 | ||||
3515 | snap = isl_tab_snap(tab); | |||
3516 | ||||
3517 | con = isl_tab_add_row(tab, ineq); | |||
3518 | if (con < 0) | |||
3519 | goto error; | |||
3520 | ||||
3521 | row = tab->con[con].index; | |||
3522 | if (isl_tab_row_is_redundant(tab, row)) | |||
3523 | type = isl_ineq_redundant; | |||
3524 | else if (isl_int_is_neg(tab->mat->row[row][1])(isl_sioimath_sgn(*(tab->mat->row[row][1])) < 0) && | |||
3525 | (tab->rational || | |||
3526 | isl_int_abs_ge(tab->mat->row[row][1],(isl_sioimath_abs_cmp(*(tab->mat->row[row][1]), *(tab-> mat->row[row][0])) >= 0) | |||
3527 | tab->mat->row[row][0])(isl_sioimath_abs_cmp(*(tab->mat->row[row][1]), *(tab-> mat->row[row][0])) >= 0))) { | |||
3528 | int nonneg = at_least_zero(tab, &tab->con[con]); | |||
3529 | if (nonneg < 0) | |||
3530 | goto error; | |||
3531 | if (nonneg) | |||
3532 | type = isl_ineq_cut; | |||
3533 | else | |||
3534 | type = separation_type(tab, row); | |||
3535 | } else { | |||
3536 | int red = con_is_redundant(tab, &tab->con[con]); | |||
3537 | if (red < 0) | |||
3538 | goto error; | |||
3539 | if (!red) | |||
3540 | type = isl_ineq_cut; | |||
3541 | else | |||
3542 | type = isl_ineq_redundant; | |||
3543 | } | |||
3544 | ||||
3545 | if (isl_tab_rollback(tab, snap)) | |||
3546 | return isl_ineq_error; | |||
3547 | return type; | |||
3548 | error: | |||
3549 | return isl_ineq_error; | |||
3550 | } | |||
3551 | ||||
3552 | int isl_tab_track_bmap(struct isl_tab *tab, __isl_take isl_basic_map *bmap) | |||
3553 | { | |||
3554 | bmap = isl_basic_map_cow(bmap); | |||
3555 | if (!tab || !bmap) | |||
3556 | goto error; | |||
3557 | ||||
3558 | if (tab->empty) { | |||
3559 | bmap = isl_basic_map_set_to_empty(bmap); | |||
3560 | if (!bmap) | |||
3561 | goto error; | |||
3562 | tab->bmap = bmap; | |||
3563 | return 0; | |||
3564 | } | |||
3565 | ||||
3566 | isl_assert(tab->mat->ctx, tab->n_eq == bmap->n_eq, goto error)do { if (tab->n_eq == bmap->n_eq) break; do { isl_handle_error (tab->mat->ctx, isl_error_unknown, "Assertion \"" "tab->n_eq == bmap->n_eq" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3566); goto error; } while (0); } while (0); | |||
3567 | isl_assert(tab->mat->ctx,do { if (tab->n_con == bmap->n_eq + bmap->n_ineq) break ; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "tab->n_con == bmap->n_eq + bmap->n_ineq" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3568); goto error; } while (0); } while (0) | |||
3568 | tab->n_con == bmap->n_eq + bmap->n_ineq, goto error)do { if (tab->n_con == bmap->n_eq + bmap->n_ineq) break ; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "tab->n_con == bmap->n_eq + bmap->n_ineq" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/tools/polly/lib/External/isl/isl_tab.c" , 3568); goto error; } while (0); } while (0); | |||
3569 | ||||
3570 | tab->bmap = bmap; | |||
3571 | ||||
3572 | return 0; | |||
3573 | error: | |||
3574 | isl_basic_map_free(bmap); | |||
3575 | return -1; | |||
3576 | } | |||
3577 | ||||
3578 | int isl_tab_track_bset(struct isl_tab *tab, __isl_take isl_basic_setisl_basic_map *bset) | |||
3579 | { | |||
3580 | return isl_tab_track_bmap(tab, (isl_basic_map *)bset); | |||
3581 | } | |||
3582 | ||||
3583 | __isl_keep isl_basic_setisl_basic_map *isl_tab_peek_bset(struct isl_tab *tab) | |||
3584 | { | |||
3585 | if (!tab) | |||
3586 | return NULL((void*)0); | |||
3587 | ||||
3588 | return (isl_basic_setisl_basic_map *)tab->bmap; | |||
3589 | } | |||
3590 | ||||
3591 | static void isl_tab_print_internal(__isl_keep struct isl_tab *tab, | |||
3592 | FILE *out, int indent) | |||
3593 | { | |||
3594 | unsigned r, c; | |||
3595 | int i; | |||
3596 | ||||
3597 | if (!tab) { | |||
3598 | fprintf(out, "%*snull tab\n", indent, ""); | |||
3599 | return; | |||
3600 | } | |||
3601 | fprintf(out, "%*sn_redundant: %d, n_dead: %d", indent, "", | |||
3602 | tab->n_redundant, tab->n_dead); | |||
3603 | if (tab->rational) | |||
3604 | fprintf(out, ", rational"); | |||
3605 | if (tab->empty) | |||
3606 | fprintf(out, ", empty"); | |||
3607 | fprintf(out, "\n"); | |||
3608 | fprintf(out, "%*s[", indent, ""); | |||
3609 | for (i = 0; i < tab->n_var; ++i) { | |||
3610 | if (i) | |||
3611 | fprintf(out, (i == tab->n_param || | |||
3612 | i == tab->n_var - tab->n_div) ? "; " | |||
3613 | : ", "); | |||
3614 | fprintf(out, "%c%d%s", tab->var[i].is_row ? 'r' : 'c', | |||
3615 | tab->var[i].index, | |||
3616 | tab->var[i].is_zero ? " [=0]" : | |||
3617 | tab->var[i].is_redundant ? " [R]" : ""); | |||
3618 | } | |||
3619 | fprintf(out, "]\n"); | |||
3620 | fprintf(out, "%*s[", indent, ""); | |||
3621 | for (i = 0; i < tab->n_con; ++i) { | |||
3622 | if (i) | |||
3623 | fprintf(out, ", "); | |||
3624 | fprintf(out, "%c%d%s", tab->con[i].is_row ? 'r' : 'c', | |||
3625 | tab->con[i].index, | |||
3626 | tab->con[i].is_zero ? " [=0]" : | |||
3627 | tab->con[i].is_redundant ? " [R]" : ""); | |||
3628 | } | |||
3629 | fprintf(out, "]\n"); | |||
3630 | fprintf(out, "%*s[", indent, ""); | |||
3631 | for (i = 0; i < tab->n_row; ++i) { | |||
3632 | const char *sign = ""; | |||
3633 | if (i) | |||
3634 | fprintf(out, ", "); | |||
3635 | if (tab->row_sign) { | |||
3636 | if (tab->row_sign[i] == isl_tab_row_unknown) | |||
3637 | sign = "?"; | |||
3638 | else if (tab->row_sign[i] == isl_tab_row_neg) | |||
3639 | sign = "-"; | |||
3640 | else if (tab->row_sign[i] == isl_tab_row_pos) | |||
3641 | sign = "+"; | |||
3642 | else | |||
3643 | sign = "+-"; | |||
3644 | } | |||
3645 | fprintf(out, "r%d: %d%s%s", i, tab->row_var[i], | |||
3646 | isl_tab_var_from_row(tab, i)->is_nonneg ? " [>=0]" : "", sign); | |||
3647 | } | |||
3648 | fprintf(out, "]\n"); | |||
3649 | fprintf(out, "%*s[", indent, ""); | |||
3650 | for (i = 0; i < tab->n_col; ++i) { | |||
3651 | if (i) | |||
3652 | fprintf(out, ", "); | |||
3653 | fprintf(out, "c%d: %d%s", i, tab->col_var[i], | |||
3654 | var_from_col(tab, i)->is_nonneg ? " [>=0]" : ""); | |||
3655 | } | |||
3656 | fprintf(out, "]\n"); | |||
3657 | r = tab->mat->n_row; | |||
3658 | tab->mat->n_row = tab->n_row; | |||
3659 | c = tab->mat->n_col; | |||
3660 | tab->mat->n_col = 2 + tab->M + tab->n_col; | |||
3661 | isl_mat_print_internal(tab->mat, out, indent); | |||
3662 | tab->mat->n_row = r; | |||
3663 | tab->mat->n_col = c; | |||
3664 | if (tab->bmap) | |||
3665 | isl_basic_map_print_internal(tab->bmap, out, indent); | |||
3666 | } | |||
3667 | ||||
3668 | void isl_tab_dump(__isl_keep struct isl_tab *tab) | |||
3669 | { | |||
3670 | isl_tab_print_internal(tab, stderrstderr, 0); | |||
3671 | } |