Coverage Report

Created: 2018-10-23 03:11

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_local_space.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2011      INRIA Saclay
3
 * Copyright 2012-2014 Ecole Normale Superieure
4
 *
5
 * Use of this software is governed by the MIT license
6
 *
7
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9
 * 91893 Orsay, France
10
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
11
 */
12
13
#include <isl_ctx_private.h>
14
#include <isl/id.h>
15
#include <isl_map_private.h>
16
#include <isl_local_space_private.h>
17
#include <isl_space_private.h>
18
#include <isl_mat_private.h>
19
#include <isl_aff_private.h>
20
#include <isl_vec_private.h>
21
#include <isl_point_private.h>
22
#include <isl_seq.h>
23
#include <isl_local.h>
24
25
isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
26
2.04M
{
27
2.04M
  return ls ? ls->dim->ctx : NULL;
28
2.04M
}
29
30
/* Return a hash value that digests "ls".
31
 */
32
uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls)
33
0
{
34
0
  uint32_t hash, space_hash, div_hash;
35
0
36
0
  if (!ls)
37
0
    return 0;
38
0
39
0
  hash = isl_hash_init();
40
0
  space_hash = isl_space_get_hash(ls->dim);
41
0
  isl_hash_hash(hash, space_hash);
42
0
  div_hash = isl_mat_get_hash(ls->div);
43
0
  isl_hash_hash(hash, div_hash);
44
0
45
0
  return hash;
46
0
}
47
48
__isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim,
49
  __isl_take isl_mat *div)
50
329k
{
51
329k
  isl_ctx *ctx;
52
329k
  isl_local_space *ls = NULL;
53
329k
54
329k
  if (!dim || !div)
55
0
    goto error;
56
329k
57
329k
  ctx = isl_space_get_ctx(dim);
58
329k
  ls = isl_calloc_type(ctx, struct isl_local_space);
59
329k
  if (!ls)
60
0
    goto error;
61
329k
62
329k
  ls->ref = 1;
63
329k
  ls->dim = dim;
64
329k
  ls->div = div;
65
329k
66
329k
  return ls;
67
0
error:
68
0
  isl_mat_free(div);
69
0
  isl_space_free(dim);
70
0
  isl_local_space_free(ls);
71
0
  return NULL;
72
329k
}
73
74
__isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim,
75
  unsigned n_div)
76
126k
{
77
126k
  isl_ctx *ctx;
78
126k
  isl_mat *div;
79
126k
  unsigned total;
80
126k
81
126k
  if (!dim)
82
3
    return NULL;
83
126k
84
126k
  total = isl_space_dim(dim, isl_dim_all);
85
126k
86
126k
  ctx = isl_space_get_ctx(dim);
87
126k
  div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
88
126k
  return isl_local_space_alloc_div(dim, div);
89
126k
}
90
91
__isl_give isl_local_space *isl_local_space_from_space(__isl_take isl_space *dim)
92
109k
{
93
109k
  return isl_local_space_alloc(dim, 0);
94
109k
}
95
96
__isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
97
467k
{
98
467k
  if (!ls)
99
0
    return NULL;
100
467k
101
467k
  ls->ref++;
102
467k
  return ls;
103
467k
}
104
105
__isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
106
147k
{
107
147k
  if (!ls)
108
0
    return NULL;
109
147k
110
147k
  return isl_local_space_alloc_div(isl_space_copy(ls->dim),
111
147k
           isl_mat_copy(ls->div));
112
147k
113
147k
}
114
115
__isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
116
345k
{
117
345k
  if (!ls)
118
0
    return NULL;
119
345k
120
345k
  if (ls->ref == 1)
121
198k
    return ls;
122
147k
  ls->ref--;
123
147k
  return isl_local_space_dup(ls);
124
147k
}
125
126
__isl_null isl_local_space *isl_local_space_free(
127
  __isl_take isl_local_space *ls)
128
648k
{
129
648k
  if (!ls)
130
0
    return NULL;
131
648k
132
648k
  if (--ls->ref > 0)
133
319k
    return NULL;
134
328k
135
328k
  isl_space_free(ls->dim);
136
328k
  isl_mat_free(ls->div);
137
328k
138
328k
  free(ls);
139
328k
140
328k
  return NULL;
141
328k
}
142
143
/* Is the local space that of a parameter domain?
144
 */
145
isl_bool isl_local_space_is_params(__isl_keep isl_local_space *ls)
146
0
{
147
0
  if (!ls)
148
0
    return isl_bool_error;
149
0
  return isl_space_is_params(ls->dim);
150
0
}
151
152
/* Is the local space that of a set?
153
 */
154
isl_bool isl_local_space_is_set(__isl_keep isl_local_space *ls)
155
176k
{
156
176k
  return ls ? isl_space_is_set(ls->dim) : 
isl_bool_error0
;
157
176k
}
158
159
/* Do "ls1" and "ls2" have the same space?
160
 */
161
isl_bool isl_local_space_has_equal_space(__isl_keep isl_local_space *ls1,
162
  __isl_keep isl_local_space *ls2)
163
1.50M
{
164
1.50M
  if (!ls1 || !ls2)
165
0
    return isl_bool_error;
166
1.50M
167
1.50M
  return isl_space_is_equal(ls1->dim, ls2->dim);
168
1.50M
}
169
170
/* Is the space of "ls" equal to "space"?
171
 */
172
isl_bool isl_local_space_has_space(__isl_keep isl_local_space *ls,
173
  __isl_keep isl_space *space)
174
19
{
175
19
  return isl_space_is_equal(isl_local_space_peek_space(ls), space);
176
19
}
177
178
/* Check that the space of "ls" is equal to "space".
179
 */
180
static isl_stat isl_local_space_check_has_space(__isl_keep isl_local_space *ls,
181
  __isl_keep isl_space *space)
182
19
{
183
19
  isl_bool ok;
184
19
185
19
  ok = isl_local_space_has_space(ls, space);
186
19
  if (ok < 0)
187
0
    return isl_stat_error;
188
19
  if (!ok)
189
19
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
190
19
      "spaces don't match", return isl_stat_error);
191
19
  return isl_stat_ok;
192
19
}
193
194
/* Return true if the two local spaces are identical, with identical
195
 * expressions for the integer divisions.
196
 */
197
isl_bool isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
198
  __isl_keep isl_local_space *ls2)
199
53.5k
{
200
53.5k
  isl_bool equal;
201
53.5k
202
53.5k
  equal = isl_local_space_has_equal_space(ls1, ls2);
203
53.5k
  if (equal < 0 || !equal)
204
0
    return equal;
205
53.5k
206
53.5k
  if (!isl_local_space_divs_known(ls1))
207
0
    return isl_bool_false;
208
53.5k
  if (!isl_local_space_divs_known(ls2))
209
0
    return isl_bool_false;
210
53.5k
211
53.5k
  return isl_mat_is_equal(ls1->div, ls2->div);
212
53.5k
}
213
214
/* Compare two isl_local_spaces.
215
 *
216
 * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater"
217
 * than "ls2" and 0 if they are equal.
218
 */
219
int isl_local_space_cmp(__isl_keep isl_local_space *ls1,
220
  __isl_keep isl_local_space *ls2)
221
17.9k
{
222
17.9k
  int cmp;
223
17.9k
224
17.9k
  if (ls1 == ls2)
225
26
    return 0;
226
17.9k
  if (!ls1)
227
0
    return -1;
228
17.9k
  if (!ls2)
229
0
    return 1;
230
17.9k
231
17.9k
  cmp = isl_space_cmp(ls1->dim, ls2->dim);
232
17.9k
  if (cmp != 0)
233
0
    return cmp;
234
17.9k
235
17.9k
  return isl_local_cmp(ls1->div, ls2->div);
236
17.9k
}
237
238
int isl_local_space_dim(__isl_keep isl_local_space *ls,
239
  enum isl_dim_type type)
240
2.98M
{
241
2.98M
  if (!ls)
242
0
    return 0;
243
2.98M
  if (type == isl_dim_div)
244
2.25M
    return ls->div->n_row;
245
735k
  if (type == isl_dim_all)
246
278k
    return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
247
457k
  return isl_space_dim(ls->dim, type);
248
457k
}
249
250
unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
251
  enum isl_dim_type type)
252
517k
{
253
517k
  isl_space *dim;
254
517k
255
517k
  if (!ls)
256
0
    return 0;
257
517k
258
517k
  dim = ls->dim;
259
517k
  switch (type) {
260
517k
  
case isl_dim_cst: return 00
;
261
517k
  
case isl_dim_param: return 117.9k
;
262
517k
  
case isl_dim_in: return 1 + dim->nparam28.5k
;
263
517k
  
case isl_dim_out: return 1 + dim->nparam + dim->n_in269k
;
264
517k
  
case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out200k
;
265
517k
  
default: return 00
;
266
517k
  }
267
517k
}
268
269
/* Return the position of the dimension of the given type and name
270
 * in "ls".
271
 * Return -1 if no such dimension can be found.
272
 */
273
int isl_local_space_find_dim_by_name(__isl_keep isl_local_space *ls,
274
  enum isl_dim_type type, const char *name)
275
0
{
276
0
  if (!ls)
277
0
    return -1;
278
0
  if (type == isl_dim_div)
279
0
    return -1;
280
0
  return isl_space_find_dim_by_name(ls->dim, type, name);
281
0
}
282
283
/* Does the given dimension have a name?
284
 */
285
isl_bool isl_local_space_has_dim_name(__isl_keep isl_local_space *ls,
286
  enum isl_dim_type type, unsigned pos)
287
0
{
288
0
  return ls ? isl_space_has_dim_name(ls->dim, type, pos) : isl_bool_error;
289
0
}
290
291
const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
292
  enum isl_dim_type type, unsigned pos)
293
0
{
294
0
  return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;
295
0
}
296
297
isl_bool isl_local_space_has_dim_id(__isl_keep isl_local_space *ls,
298
  enum isl_dim_type type, unsigned pos)
299
1.21k
{
300
1.21k
  return ls ? isl_space_has_dim_id(ls->dim, type, pos) : 
isl_bool_error0
;
301
1.21k
}
302
303
__isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls,
304
  enum isl_dim_type type, unsigned pos)
305
1.21k
{
306
1.21k
  return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL;
307
1.21k
}
308
309
/* Return the argument of the integer division at position "pos" in "ls".
310
 * All local variables in "ls" are known to have a (complete) explicit
311
 * representation.
312
 */
313
static __isl_give isl_aff *extract_div(__isl_keep isl_local_space *ls, int pos)
314
713
{
315
713
  isl_aff *aff;
316
713
317
713
  aff = isl_aff_alloc(isl_local_space_copy(ls));
318
713
  if (!aff)
319
0
    return NULL;
320
713
  isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
321
713
  return aff;
322
713
}
323
324
/* Return the argument of the integer division at position "pos" in "ls".
325
 * The integer division at that position is known to have a complete
326
 * explicit representation, but some of the others do not.
327
 * Remove them first because the domain of an isl_aff
328
 * is not allowed to have unknown local variables.
329
 */
330
static __isl_give isl_aff *drop_unknown_divs_and_extract_div(
331
  __isl_keep isl_local_space *ls, int pos)
332
0
{
333
0
  int i, n;
334
0
  isl_bool unknown;
335
0
  isl_aff *aff;
336
0
337
0
  ls = isl_local_space_copy(ls);
338
0
  n = isl_local_space_dim(ls, isl_dim_div);
339
0
  for (i = n - 1; i >= 0; --i) {
340
0
    unknown = isl_local_space_div_is_marked_unknown(ls, i);
341
0
    if (unknown < 0)
342
0
      ls = isl_local_space_free(ls);
343
0
    else if (!unknown)
344
0
      continue;
345
0
    ls = isl_local_space_drop_dims(ls, isl_dim_div, i, 1);
346
0
    if (pos > i)
347
0
      --pos;
348
0
  }
349
0
  aff = extract_div(ls, pos);
350
0
  isl_local_space_free(ls);
351
0
  return aff;
352
0
}
353
354
/* Return the argument of the integer division at position "pos" in "ls".
355
 * The integer division is assumed to have a complete explicit
356
 * representation.  If some of the other integer divisions
357
 * do not have an explicit representation, then they need
358
 * to be removed first because the domain of an isl_aff
359
 * is not allowed to have unknown local variables.
360
 */
361
__isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
362
  int pos)
363
713
{
364
713
  isl_bool known;
365
713
366
713
  if (!ls)
367
0
    return NULL;
368
713
369
713
  if (pos < 0 || pos >= ls->div->n_row)
370
713
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
371
713
      "index out of bounds", return NULL);
372
713
373
713
  known = isl_local_space_div_is_known(ls, pos);
374
713
  if (known < 0)
375
0
    return NULL;
376
713
  if (!known)
377
713
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
378
713
      "expression of div unknown", return NULL);
379
713
  if (!isl_local_space_is_set(ls))
380
713
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
381
713
      "cannot represent divs of map spaces", return NULL);
382
713
383
713
  known = isl_local_space_divs_known(ls);
384
713
  if (known < 0)
385
0
    return NULL;
386
713
  if (known)
387
713
    return extract_div(ls, pos);
388
0
  else
389
0
    return drop_unknown_divs_and_extract_div(ls, pos);
390
713
}
391
392
/* Return the space of "ls".
393
 */
394
__isl_keep isl_space *isl_local_space_peek_space(__isl_keep isl_local_space *ls)
395
2.56M
{
396
2.56M
  if (!ls)
397
0
    return NULL;
398
2.56M
399
2.56M
  return ls->dim;
400
2.56M
}
401
402
__isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
403
584k
{
404
584k
  return isl_space_copy(isl_local_space_peek_space(ls));
405
584k
}
406
407
/* Return the space of "ls".
408
 * This may be either a copy or the space itself
409
 * if there is only one reference to "ls".
410
 * This allows the space to be modified inplace
411
 * if both the local space and its space have only a single reference.
412
 * The caller is not allowed to modify "ls" between this call and
413
 * a subsequent call to isl_local_space_restore_space.
414
 * The only exception is that isl_local_space_free can be called instead.
415
 */
416
__isl_give isl_space *isl_local_space_take_space(__isl_keep isl_local_space *ls)
417
0
{
418
0
  isl_space *space;
419
0
420
0
  if (!ls)
421
0
    return NULL;
422
0
  if (ls->ref != 1)
423
0
    return isl_local_space_get_space(ls);
424
0
  space = ls->dim;
425
0
  ls->dim = NULL;
426
0
  return space;
427
0
}
428
429
/* Set the space of "ls" to "space", where the space of "ls" may be missing
430
 * due to a preceding call to isl_local_space_take_space.
431
 * However, in this case, "ls" only has a single reference and
432
 * then the call to isl_local_space_cow has no effect.
433
 */
434
__isl_give isl_local_space *isl_local_space_restore_space(
435
  __isl_take isl_local_space *ls, __isl_take isl_space *space)
436
0
{
437
0
  if (!ls || !space)
438
0
    goto error;
439
0
440
0
  if (ls->dim == space) {
441
0
    isl_space_free(space);
442
0
    return ls;
443
0
  }
444
0
445
0
  ls = isl_local_space_cow(ls);
446
0
  if (!ls)
447
0
    goto error;
448
0
  isl_space_free(ls->dim);
449
0
  ls->dim = space;
450
0
451
0
  return ls;
452
0
error:
453
0
  isl_local_space_free(ls);
454
0
  isl_space_free(space);
455
0
  return NULL;
456
0
}
457
458
/* Return the local variables of "ls".
459
 */
460
__isl_keep isl_local *isl_local_space_peek_local(__isl_keep isl_local_space *ls)
461
19
{
462
19
  return ls ? ls->div : NULL;
463
19
}
464
465
/* Replace the identifier of the tuple of type "type" by "id".
466
 */
467
__isl_give isl_local_space *isl_local_space_set_tuple_id(
468
  __isl_take isl_local_space *ls,
469
  enum isl_dim_type type, __isl_take isl_id *id)
470
1
{
471
1
  ls = isl_local_space_cow(ls);
472
1
  if (!ls)
473
0
    goto error;
474
1
  ls->dim = isl_space_set_tuple_id(ls->dim, type, id);
475
1
  if (!ls->dim)
476
0
    return isl_local_space_free(ls);
477
1
  return ls;
478
0
error:
479
0
  isl_id_free(id);
480
0
  return NULL;
481
1
}
482
483
__isl_give isl_local_space *isl_local_space_set_dim_name(
484
  __isl_take isl_local_space *ls,
485
  enum isl_dim_type type, unsigned pos, const char *s)
486
0
{
487
0
  ls = isl_local_space_cow(ls);
488
0
  if (!ls)
489
0
    return NULL;
490
0
  ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);
491
0
  if (!ls->dim)
492
0
    return isl_local_space_free(ls);
493
0
494
0
  return ls;
495
0
}
496
497
__isl_give isl_local_space *isl_local_space_set_dim_id(
498
  __isl_take isl_local_space *ls,
499
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
500
0
{
501
0
  ls = isl_local_space_cow(ls);
502
0
  if (!ls)
503
0
    goto error;
504
0
  ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);
505
0
  if (!ls->dim)
506
0
    return isl_local_space_free(ls);
507
0
508
0
  return ls;
509
0
error:
510
0
  isl_id_free(id);
511
0
  return NULL;
512
0
}
513
514
/* Construct a zero-dimensional local space with the given parameter domain.
515
 */
516
__isl_give isl_local_space *isl_local_space_set_from_params(
517
  __isl_take isl_local_space *ls)
518
0
{
519
0
  isl_space *space;
520
0
521
0
  space = isl_local_space_take_space(ls);
522
0
  space = isl_space_set_from_params(space);
523
0
  ls = isl_local_space_restore_space(ls, space);
524
0
525
0
  return ls;
526
0
}
527
528
__isl_give isl_local_space *isl_local_space_reset_space(
529
  __isl_take isl_local_space *ls, __isl_take isl_space *dim)
530
96.1k
{
531
96.1k
  ls = isl_local_space_cow(ls);
532
96.1k
  if (!ls || !dim)
533
0
    goto error;
534
96.1k
535
96.1k
  isl_space_free(ls->dim);
536
96.1k
  ls->dim = dim;
537
96.1k
538
96.1k
  return ls;
539
0
error:
540
0
  isl_local_space_free(ls);
541
0
  isl_space_free(dim);
542
0
  return NULL;
543
96.1k
}
544
545
/* Reorder the dimensions of "ls" according to the given reordering.
546
 * The reordering r is assumed to have been extended with the local
547
 * variables, leaving them in the same order.
548
 */
549
__isl_give isl_local_space *isl_local_space_realign(
550
  __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
551
10.2k
{
552
10.2k
  ls = isl_local_space_cow(ls);
553
10.2k
  if (!ls || !r)
554
0
    goto error;
555
10.2k
556
10.2k
  ls->div = isl_local_reorder(ls->div, isl_reordering_copy(r));
557
10.2k
  if (!ls->div)
558
0
    goto error;
559
10.2k
560
10.2k
  ls = isl_local_space_reset_space(ls, isl_reordering_get_space(r));
561
10.2k
562
10.2k
  isl_reordering_free(r);
563
10.2k
  return ls;
564
0
error:
565
0
  isl_local_space_free(ls);
566
0
  isl_reordering_free(r);
567
0
  return NULL;
568
10.2k
}
569
570
__isl_give isl_local_space *isl_local_space_add_div(
571
  __isl_take isl_local_space *ls, __isl_take isl_vec *div)
572
4.20k
{
573
4.20k
  ls = isl_local_space_cow(ls);
574
4.20k
  if (!ls || !div)
575
0
    goto error;
576
4.20k
577
4.20k
  if (ls->div->n_col != div->size)
578
4.20k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
579
4.20k
      "incompatible dimensions", goto error);
580
4.20k
581
4.20k
  ls->div = isl_mat_add_zero_cols(ls->div, 1);
582
4.20k
  ls->div = isl_mat_add_rows(ls->div, 1);
583
4.20k
  if (!ls->div)
584
0
    goto error;
585
4.20k
586
4.20k
  isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
587
4.20k
  isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
588
4.20k
589
4.20k
  isl_vec_free(div);
590
4.20k
  return ls;
591
0
error:
592
0
  isl_local_space_free(ls);
593
0
  isl_vec_free(div);
594
0
  return NULL;
595
4.20k
}
596
597
__isl_give isl_local_space *isl_local_space_replace_divs(
598
  __isl_take isl_local_space *ls, __isl_take isl_mat *div)
599
46.9k
{
600
46.9k
  ls = isl_local_space_cow(ls);
601
46.9k
602
46.9k
  if (!ls || !div)
603
0
    goto error;
604
46.9k
605
46.9k
  isl_mat_free(ls->div);
606
46.9k
  ls->div = div;
607
46.9k
  return ls;
608
0
error:
609
0
  isl_mat_free(div);
610
0
  isl_local_space_free(ls);
611
0
  return NULL;
612
46.9k
}
613
614
/* Copy row "s" of "src" to row "d" of "dst", applying the expansion
615
 * defined by "exp".
616
 */
617
static void expand_row(__isl_keep isl_mat *dst, int d,
618
  __isl_keep isl_mat *src, int s, int *exp)
619
38.7k
{
620
38.7k
  int i;
621
38.7k
  unsigned c = src->n_col - src->n_row;
622
38.7k
623
38.7k
  isl_seq_cpy(dst->row[d], src->row[s], c);
624
38.7k
  isl_seq_clr(dst->row[d] + c, dst->n_col - c);
625
38.7k
626
41.4k
  for (i = 0; i < s; 
++i2.74k
)
627
38.7k
    
isl_int_set2.74k
(dst->row[d][c + exp[i]], src->row[s][c + i]);
628
38.7k
}
629
630
/* Compare (known) divs.
631
 * Return non-zero if at least one of the two divs is unknown.
632
 * In particular, if both divs are unknown, we respect their
633
 * current order.  Otherwise, we sort the known div after the unknown
634
 * div only if the known div depends on the unknown div.
635
 */
636
static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,
637
  unsigned n_row, unsigned n_col)
638
13.0k
{
639
13.0k
  int li, lj;
640
13.0k
  int unknown_i, unknown_j;
641
13.0k
642
13.0k
  unknown_i = isl_int_is_zero(row_i[0]);
643
13.0k
  unknown_j = isl_int_is_zero(row_j[0]);
644
13.0k
645
13.0k
  if (unknown_i && 
unknown_j5.59k
)
646
1.44k
    return i - j;
647
11.6k
648
11.6k
  if (unknown_i)
649
4.14k
    li = n_col - n_row + i;
650
7.48k
  else
651
7.48k
    li = isl_seq_last_non_zero(row_i, n_col);
652
11.6k
  if (unknown_j)
653
814
    lj = n_col - n_row + j;
654
10.8k
  else
655
10.8k
    lj = isl_seq_last_non_zero(row_j, n_col);
656
11.6k
657
11.6k
  if (li != lj)
658
6.01k
    return li - lj;
659
5.62k
660
5.62k
  return isl_seq_cmp(row_i, row_j, n_col);
661
5.62k
}
662
663
/* Call cmp_row for divs in a matrix.
664
 */
665
int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j)
666
4.29k
{
667
4.29k
  return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col);
668
4.29k
}
669
670
/* Call cmp_row for divs in a basic map.
671
 */
672
static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,
673
  unsigned total)
674
8.79k
{
675
8.79k
  return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total);
676
8.79k
}
677
678
/* Sort the divs in "bmap".
679
 *
680
 * We first make sure divs are placed after divs on which they depend.
681
 * Then we perform a simple insertion sort based on the same ordering
682
 * that is used in isl_merge_divs.
683
 */
684
__isl_give isl_basic_map *isl_basic_map_sort_divs(
685
  __isl_take isl_basic_map *bmap)
686
64.0k
{
687
64.0k
  int i, j;
688
64.0k
  unsigned total;
689
64.0k
690
64.0k
  bmap = isl_basic_map_order_divs(bmap);
691
64.0k
  if (!bmap)
692
0
    return NULL;
693
64.0k
  if (bmap->n_div <= 1)
694
60.2k
    return bmap;
695
3.76k
696
3.76k
  total = 2 + isl_basic_map_total_dim(bmap);
697
10.8k
  for (i = 1; i < bmap->n_div; 
++i7.06k
) {
698
9.78k
    for (j = i - 1; j >= 0; 
--j2.72k
) {
699
8.79k
      if (bmap_cmp_row(bmap, j, j + 1, total) <= 0)
700
6.07k
        break;
701
2.72k
      isl_basic_map_swap_div(bmap, j, j + 1);
702
2.72k
    }
703
7.06k
  }
704
3.76k
705
3.76k
  return bmap;
706
3.76k
}
707
708
/* Sort the divs in the basic maps of "map".
709
 */
710
__isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)
711
24.3k
{
712
24.3k
  return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs);
713
24.3k
}
714
715
/* Combine the two lists of divs into a single list.
716
 * For each row i in div1, exp1[i] is set to the position of the corresponding
717
 * row in the result.  Similarly for div2 and exp2.
718
 * This function guarantees
719
 *  exp1[i] >= i
720
 *  exp1[i+1] > exp1[i]
721
 * For optimal merging, the two input list should have been sorted.
722
 */
723
__isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
724
  __isl_keep isl_mat *div2, int *exp1, int *exp2)
725
35.4k
{
726
35.4k
  int i, j, k;
727
35.4k
  isl_mat *div = NULL;
728
35.4k
  unsigned d;
729
35.4k
730
35.4k
  if (!div1 || !div2)
731
0
    return NULL;
732
35.4k
733
35.4k
  d = div1->n_col - div1->n_row;
734
35.4k
  div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
735
35.4k
        d + div1->n_row + div2->n_row);
736
35.4k
  if (!div)
737
0
    return NULL;
738
35.4k
739
37.0k
  
for (i = 0, j = 0, k = 0; 35.4k
i < div1->n_row &&
j < div2->n_row21.5k
;
++k1.68k
) {
740
1.68k
    int cmp;
741
1.68k
742
1.68k
    expand_row(div, k, div1, i, exp1);
743
1.68k
    expand_row(div, k + 1, div2, j, exp2);
744
1.68k
745
1.68k
    cmp = isl_mat_cmp_div(div, k, k + 1);
746
1.68k
    if (cmp == 0) {
747
1.06k
      exp1[i++] = k;
748
1.06k
      exp2[j++] = k;
749
1.06k
    } else 
if (611
cmp < 0611
) {
750
131
      exp1[i++] = k;
751
480
    } else {
752
480
      exp2[j++] = k;
753
480
      isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
754
480
    }
755
1.68k
  }
756
55.6k
  for (; i < div1->n_row; 
++i, ++k20.2k
) {
757
20.2k
    expand_row(div, k, div1, i, exp1);
758
20.2k
    exp1[i] = k;
759
20.2k
  }
760
50.5k
  for (; j < div2->n_row; 
++j, ++k15.1k
) {
761
15.1k
    expand_row(div, k, div2, j, exp2);
762
15.1k
    exp2[j] = k;
763
15.1k
  }
764
35.4k
765
35.4k
  div->n_row = k;
766
35.4k
  div->n_col = d + k;
767
35.4k
768
35.4k
  return div;
769
35.4k
}
770
771
/* Swap divs "a" and "b" in "ls".
772
 */
773
__isl_give isl_local_space *isl_local_space_swap_div(
774
  __isl_take isl_local_space *ls, int a, int b)
775
1.15k
{
776
1.15k
  int offset;
777
1.15k
778
1.15k
  ls = isl_local_space_cow(ls);
779
1.15k
  if (!ls)
780
0
    return NULL;
781
1.15k
  if (a < 0 || a >= ls->div->n_row || b < 0 || b >= ls->div->n_row)
782
1.15k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
783
1.15k
      "index out of bounds", return isl_local_space_free(ls));
784
1.15k
  offset = ls->div->n_col - ls->div->n_row;
785
1.15k
  ls->div = isl_mat_swap_cols(ls->div, offset + a, offset + b);
786
1.15k
  ls->div = isl_mat_swap_rows(ls->div, a, b);
787
1.15k
  if (!ls->div)
788
0
    return isl_local_space_free(ls);
789
1.15k
  return ls;
790
1.15k
}
791
792
/* Construct a local space that contains all the divs in either
793
 * "ls1" or "ls2".
794
 */
795
__isl_give isl_local_space *isl_local_space_intersect(
796
  __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
797
0
{
798
0
  isl_ctx *ctx;
799
0
  int *exp1 = NULL;
800
0
  int *exp2 = NULL;
801
0
  isl_mat *div = NULL;
802
0
  isl_bool equal;
803
0
804
0
  if (!ls1 || !ls2)
805
0
    goto error;
806
0
807
0
  ctx = isl_local_space_get_ctx(ls1);
808
0
  if (!isl_space_is_equal(ls1->dim, ls2->dim))
809
0
    isl_die(ctx, isl_error_invalid,
810
0
      "spaces should be identical", goto error);
811
0
812
0
  if (ls2->div->n_row == 0) {
813
0
    isl_local_space_free(ls2);
814
0
    return ls1;
815
0
  }
816
0
817
0
  if (ls1->div->n_row == 0) {
818
0
    isl_local_space_free(ls1);
819
0
    return ls2;
820
0
  }
821
0
822
0
  exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);
823
0
  exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
824
0
  if (!exp1 || !exp2)
825
0
    goto error;
826
0
827
0
  div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);
828
0
  if (!div)
829
0
    goto error;
830
0
831
0
  equal = isl_mat_is_equal(ls1->div, div);
832
0
  if (equal < 0)
833
0
    goto error;
834
0
  if (!equal)
835
0
    ls1 = isl_local_space_cow(ls1);
836
0
  if (!ls1)
837
0
    goto error;
838
0
839
0
  free(exp1);
840
0
  free(exp2);
841
0
  isl_local_space_free(ls2);
842
0
  isl_mat_free(ls1->div);
843
0
  ls1->div = div;
844
0
845
0
  return ls1;
846
0
error:
847
0
  free(exp1);
848
0
  free(exp2);
849
0
  isl_mat_free(div);
850
0
  isl_local_space_free(ls1);
851
0
  isl_local_space_free(ls2);
852
0
  return NULL;
853
0
}
854
855
/* Is the local variable "div" of "ls" marked as not having
856
 * an explicit representation?
857
 * Note that even if this variable is not marked in this way and therefore
858
 * does have an explicit representation, this representation may still
859
 * depend (indirectly) on other local variables that do not
860
 * have an explicit representation.
861
 */
862
isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls,
863
  int div)
864
262
{
865
262
  if (!ls)
866
0
    return isl_bool_error;
867
262
  return isl_local_div_is_marked_unknown(ls->div, div);
868
262
}
869
870
/* Does "ls" have a complete explicit representation for div "div"?
871
 */
872
isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div)
873
1.33k
{
874
1.33k
  if (!ls)
875
0
    return isl_bool_error;
876
1.33k
  return isl_local_div_is_known(ls->div, div);
877
1.33k
}
878
879
/* Does "ls" have an explicit representation for all local variables?
880
 */
881
isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls)
882
283k
{
883
283k
  if (!ls)
884
0
    return isl_bool_error;
885
283k
  return isl_local_divs_known(ls->div);
886
283k
}
887
888
__isl_give isl_local_space *isl_local_space_domain(
889
  __isl_take isl_local_space *ls)
890
10.0k
{
891
10.0k
  ls = isl_local_space_drop_dims(ls, isl_dim_out,
892
10.0k
          0, isl_local_space_dim(ls, isl_dim_out));
893
10.0k
  ls = isl_local_space_cow(ls);
894
10.0k
  if (!ls)
895
0
    return NULL;
896
10.0k
  ls->dim = isl_space_domain(ls->dim);
897
10.0k
  if (!ls->dim)
898
0
    return isl_local_space_free(ls);
899
10.0k
  return ls;
900
10.0k
}
901
902
__isl_give isl_local_space *isl_local_space_range(
903
  __isl_take isl_local_space *ls)
904
0
{
905
0
  ls = isl_local_space_drop_dims(ls, isl_dim_in,
906
0
          0, isl_local_space_dim(ls, isl_dim_in));
907
0
  ls = isl_local_space_cow(ls);
908
0
  if (!ls)
909
0
    return NULL;
910
0
911
0
  ls->dim = isl_space_range(ls->dim);
912
0
  if (!ls->dim)
913
0
    return isl_local_space_free(ls);
914
0
  return ls;
915
0
}
916
917
/* Construct a local space for a map that has the given local
918
 * space as domain and that has a zero-dimensional range.
919
 */
920
__isl_give isl_local_space *isl_local_space_from_domain(
921
  __isl_take isl_local_space *ls)
922
76.3k
{
923
76.3k
  ls = isl_local_space_cow(ls);
924
76.3k
  if (!ls)
925
0
    return NULL;
926
76.3k
  ls->dim = isl_space_from_domain(ls->dim);
927
76.3k
  if (!ls->dim)
928
0
    return isl_local_space_free(ls);
929
76.3k
  return ls;
930
76.3k
}
931
932
__isl_give isl_local_space *isl_local_space_add_dims(
933
  __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
934
76.3k
{
935
76.3k
  int pos;
936
76.3k
937
76.3k
  if (!ls)
938
0
    return NULL;
939
76.3k
  pos = isl_local_space_dim(ls, type);
940
76.3k
  return isl_local_space_insert_dims(ls, type, pos, n);
941
76.3k
}
942
943
/* Remove common factor of non-constant terms and denominator.
944
 */
945
static void normalize_div(__isl_keep isl_local_space *ls, int div)
946
1.02k
{
947
1.02k
  isl_ctx *ctx = ls->div->ctx;
948
1.02k
  unsigned total = ls->div->n_col - 2;
949
1.02k
950
1.02k
  isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
951
1.02k
  isl_int_gcd(ctx->normalize_gcd,
952
1.02k
        ctx->normalize_gcd, ls->div->row[div][0]);
953
1.02k
  if (isl_int_is_one(ctx->normalize_gcd))
954
1.02k
    
return527
;
955
498
956
498
  isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
957
498
          ctx->normalize_gcd, total);
958
498
  isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
959
498
          ctx->normalize_gcd);
960
498
  isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
961
498
          ctx->normalize_gcd);
962
498
}
963
964
/* Exploit the equalities in "eq" to simplify the expressions of
965
 * the integer divisions in "ls".
966
 * The integer divisions in "ls" are assumed to appear as regular
967
 * dimensions in "eq".
968
 */
969
__isl_give isl_local_space *isl_local_space_substitute_equalities(
970
  __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
971
4.80k
{
972
4.80k
  int i, j, k;
973
4.80k
  unsigned total;
974
4.80k
  unsigned n_div;
975
4.80k
976
4.80k
  if (!ls || !eq)
977
0
    goto error;
978
4.80k
979
4.80k
  total = isl_space_dim(eq->dim, isl_dim_all);
980
4.80k
  if (isl_local_space_dim(ls, isl_dim_all) != total)
981
4.80k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
982
4.80k
      "spaces don't match", goto error);
983
4.80k
  total++;
984
4.80k
  n_div = eq->n_div;
985
11.2k
  for (i = 0; i < eq->n_eq; 
++i6.43k
) {
986
6.43k
    j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
987
6.43k
    if (j < 0 || j == 0 || j >= total)
988
800
      continue;
989
5.63k
990
8.39k
    
for (k = 0; 5.63k
k < ls->div->n_row;
++k2.76k
) {
991
2.76k
      if (isl_int_is_zero(ls->div->row[k][1 + j]))
992
2.76k
        
continue2.23k
;
993
521
      ls = isl_local_space_cow(ls);
994
521
      if (!ls)
995
0
        goto error;
996
521
      ls->div = isl_mat_cow(ls->div);
997
521
      if (!ls->div)
998
0
        goto error;
999
521
      isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
1000
521
          &ls->div->row[k][0]);
1001
521
      normalize_div(ls, k);
1002
521
    }
1003
5.63k
  }
1004
4.80k
1005
4.80k
  isl_basic_set_free(eq);
1006
4.80k
  return ls;
1007
0
error:
1008
0
  isl_basic_set_free(eq);
1009
0
  isl_local_space_free(ls);
1010
0
  return NULL;
1011
4.80k
}
1012
1013
/* Plug in the affine expressions "subs" of length "subs_len" (including
1014
 * the denominator and the constant term) into the variable at position "pos"
1015
 * of the "n" div expressions starting at "first".
1016
 *
1017
 * Let i be the dimension to replace and let "subs" be of the form
1018
 *
1019
 *  f/d
1020
 *
1021
 * Any integer division starting at "first" with a non-zero coefficient for i,
1022
 *
1023
 *  floor((a i + g)/m)
1024
 *
1025
 * is replaced by
1026
 *
1027
 *  floor((a f + d g)/(m d))
1028
 */
1029
__isl_give isl_local_space *isl_local_space_substitute_seq(
1030
  __isl_take isl_local_space *ls,
1031
  enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len,
1032
  int first, int n)
1033
2.06k
{
1034
2.06k
  int i;
1035
2.06k
  isl_int v;
1036
2.06k
1037
2.06k
  if (n == 0)
1038
1.45k
    return ls;
1039
613
  ls = isl_local_space_cow(ls);
1040
613
  if (!ls)
1041
0
    return NULL;
1042
613
  ls->div = isl_mat_cow(ls->div);
1043
613
  if (!ls->div)
1044
0
    return isl_local_space_free(ls);
1045
613
1046
613
  if (first + n > ls->div->n_row)
1047
613
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
1048
613
      "index out of bounds", return isl_local_space_free(ls));
1049
613
1050
613
  pos += isl_local_space_offset(ls, type);
1051
613
1052
613
  isl_int_init(v);
1053
1.54k
  for (i = first; i < first + n; 
++i927
) {
1054
927
    if (isl_int_is_zero(ls->div->row[i][1 + pos]))
1055
927
      
continue727
;
1056
200
    isl_seq_substitute(ls->div->row[i], pos, subs,
1057
200
      ls->div->n_col, subs_len, v);
1058
200
    normalize_div(ls, i);
1059
200
  }
1060
613
  isl_int_clear(v);
1061
613
1062
613
  return ls;
1063
613
}
1064
1065
/* Plug in "subs" for dimension "type", "pos" in the integer divisions
1066
 * of "ls".
1067
 *
1068
 * Let i be the dimension to replace and let "subs" be of the form
1069
 *
1070
 *  f/d
1071
 *
1072
 * Any integer division with a non-zero coefficient for i,
1073
 *
1074
 *  floor((a i + g)/m)
1075
 *
1076
 * is replaced by
1077
 *
1078
 *  floor((a f + d g)/(m d))
1079
 */
1080
__isl_give isl_local_space *isl_local_space_substitute(
1081
  __isl_take isl_local_space *ls,
1082
  enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
1083
1.07k
{
1084
1.07k
  ls = isl_local_space_cow(ls);
1085
1.07k
  if (!ls || !subs)
1086
0
    return isl_local_space_free(ls);
1087
1.07k
1088
1.07k
  if (!isl_space_is_equal(ls->dim, subs->ls->dim))
1089
1.07k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
1090
1.07k
      "spaces don't match", return isl_local_space_free(ls));
1091
1.07k
  if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
1092
1.07k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_unsupported,
1093
1.07k
      "cannot handle divs yet",
1094
1.07k
      return isl_local_space_free(ls));
1095
1.07k
1096
1.07k
  return isl_local_space_substitute_seq(ls, type, pos, subs->v->el,
1097
1.07k
              subs->v->size, 0, ls->div->n_row);
1098
1.07k
}
1099
1100
isl_bool isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
1101
  enum isl_dim_type type)
1102
8.95k
{
1103
8.95k
  if (!ls)
1104
0
    return isl_bool_error;
1105
8.95k
  return isl_space_is_named_or_nested(ls->dim, type);
1106
8.95k
}
1107
1108
__isl_give isl_local_space *isl_local_space_drop_dims(
1109
  __isl_take isl_local_space *ls,
1110
  enum isl_dim_type type, unsigned first, unsigned n)
1111
21.3k
{
1112
21.3k
  isl_ctx *ctx;
1113
21.3k
1114
21.3k
  if (!ls)
1115
0
    return NULL;
1116
21.3k
  if (n == 0 && 
!isl_local_space_is_named_or_nested(ls, type)7.20k
)
1117
7.18k
    return ls;
1118
14.2k
1119
14.2k
  ctx = isl_local_space_get_ctx(ls);
1120
14.2k
  if (first + n > isl_local_space_dim(ls, type))
1121
14.2k
    
isl_die0
(ctx, isl_error_invalid, "range out of bounds",
1122
14.2k
      return isl_local_space_free(ls));
1123
14.2k
1124
14.2k
  ls = isl_local_space_cow(ls);
1125
14.2k
  if (!ls)
1126
0
    return NULL;
1127
14.2k
1128
14.2k
  if (type == isl_dim_div) {
1129
2.62k
    ls->div = isl_mat_drop_rows(ls->div, first, n);
1130
11.5k
  } else {
1131
11.5k
    ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
1132
11.5k
    if (!ls->dim)
1133
0
      return isl_local_space_free(ls);
1134
14.2k
  }
1135
14.2k
1136
14.2k
  first += 1 + isl_local_space_offset(ls, type);
1137
14.2k
  ls->div = isl_mat_drop_cols(ls->div, first, n);
1138
14.2k
  if (!ls->div)
1139
0
    return isl_local_space_free(ls);
1140
14.2k
1141
14.2k
  return ls;
1142
14.2k
}
1143
1144
__isl_give isl_local_space *isl_local_space_insert_dims(
1145
  __isl_take isl_local_space *ls,
1146
  enum isl_dim_type type, unsigned first, unsigned n)
1147
83.3k
{
1148
83.3k
  isl_ctx *ctx;
1149
83.3k
1150
83.3k
  if (!ls)
1151
0
    return NULL;
1152
83.3k
  if (n == 0 && 
!isl_local_space_is_named_or_nested(ls, type)4
)
1153
0
    return ls;
1154
83.3k
1155
83.3k
  ctx = isl_local_space_get_ctx(ls);
1156
83.3k
  if (first > isl_local_space_dim(ls, type))
1157
83.3k
    
isl_die0
(ctx, isl_error_invalid, "position out of bounds",
1158
83.3k
      return isl_local_space_free(ls));
1159
83.3k
1160
83.3k
  ls = isl_local_space_cow(ls);
1161
83.3k
  if (!ls)
1162
0
    return NULL;
1163
83.3k
1164
83.3k
  if (type == isl_dim_div) {
1165
0
    ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
1166
83.3k
  } else {
1167
83.3k
    ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
1168
83.3k
    if (!ls->dim)
1169
0
      return isl_local_space_free(ls);
1170
83.3k
  }
1171
83.3k
1172
83.3k
  first += 1 + isl_local_space_offset(ls, type);
1173
83.3k
  ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
1174
83.3k
  if (!ls->div)
1175
0
    return isl_local_space_free(ls);
1176
83.3k
1177
83.3k
  return ls;
1178
83.3k
}
1179
1180
/* Does the linear part of "constraint" correspond to
1181
 * integer division "div" in "ls"?
1182
 *
1183
 * That is, given div = floor((c + f)/m), is the constraint of the form
1184
 *
1185
 *    f - m d + c' >= 0   [sign = 1]
1186
 * or
1187
 *    -f + m d + c'' >= 0   [sign = -1]
1188
 * ?
1189
 * If so, set *sign to the corresponding value.
1190
 */
1191
static isl_bool is_linear_div_constraint(__isl_keep isl_local_space *ls,
1192
  isl_int *constraint, unsigned div, int *sign)
1193
262
{
1194
262
  isl_bool unknown;
1195
262
  unsigned pos;
1196
262
1197
262
  unknown = isl_local_space_div_is_marked_unknown(ls, div);
1198
262
  if (unknown < 0)
1199
0
    return isl_bool_error;
1200
262
  if (unknown)
1201
0
    return isl_bool_false;
1202
262
1203
262
  pos = isl_local_space_offset(ls, isl_dim_div) + div;
1204
262
1205
262
  if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
1206
197
    *sign = -1;
1207
197
    if (!isl_seq_is_neg(constraint + 1,
1208
197
            ls->div->row[div] + 2, pos - 1))
1209
6
      return isl_bool_false;
1210
65
  } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
1211
44
    *sign = 1;
1212
44
    if (!isl_seq_eq(constraint + 1, ls->div->row[div] + 2, pos - 1))
1213
5
      return isl_bool_false;
1214
21
  } else {
1215
21
    return isl_bool_false;
1216
21
  }
1217
230
  if (isl_seq_first_non_zero(constraint + pos + 1,
1218
230
            ls->div->n_row - div - 1) != -1)
1219
0
    return isl_bool_false;
1220
230
  return isl_bool_true;
1221
230
}
1222
1223
/* Check if the constraints pointed to by "constraint" is a div
1224
 * constraint corresponding to div "div" in "ls".
1225
 *
1226
 * That is, if div = floor(f/m), then check if the constraint is
1227
 *
1228
 *    f - m d >= 0
1229
 * or
1230
 *    -(f-(m-1)) + m d >= 0
1231
 *
1232
 * First check if the linear part is of the right form and
1233
 * then check the constant term.
1234
 */
1235
isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
1236
  isl_int *constraint, unsigned div)
1237
108
{
1238
108
  int sign;
1239
108
  isl_bool linear;
1240
108
1241
108
  linear = is_linear_div_constraint(ls, constraint, div, &sign);
1242
108
  if (linear < 0 || !linear)
1243
30
    return linear;
1244
78
1245
78
  if (sign < 0) {
1246
39
    int neg;
1247
39
    isl_int_sub(ls->div->row[div][1],
1248
39
        ls->div->row[div][1], ls->div->row[div][0]);
1249
39
    isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1250
39
    neg = isl_seq_is_neg(constraint, ls->div->row[div] + 1, 1);
1251
39
    isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1252
39
    isl_int_add(ls->div->row[div][1],
1253
39
        ls->div->row[div][1], ls->div->row[div][0]);
1254
39
    if (!neg)
1255
1
      return isl_bool_false;
1256
39
  } else {
1257
39
    if (!isl_int_eq(constraint[0], ls->div->row[div][1]))
1258
39
      
return isl_bool_false33
;
1259
44
  }
1260
44
1261
44
  return isl_bool_true;
1262
44
}
1263
1264
/* Is the constraint pointed to by "constraint" one
1265
 * of an equality that corresponds to integer division "div" in "ls"?
1266
 *
1267
 * That is, given an integer division of the form
1268
 *
1269
 *  a = floor((f + c)/m)
1270
 *
1271
 * is the equality of the form
1272
 *
1273
 *    -f + m d + c' = 0
1274
 * ?
1275
 * Note that the constant term is not checked explicitly, but given
1276
 * that this is a valid equality constraint, the constant c' necessarily
1277
 * has a value close to -c.
1278
 */
1279
isl_bool isl_local_space_is_div_equality(__isl_keep isl_local_space *ls,
1280
  isl_int *constraint, unsigned div)
1281
154
{
1282
154
  int sign;
1283
154
  isl_bool linear;
1284
154
1285
154
  linear = is_linear_div_constraint(ls, constraint, div, &sign);
1286
154
  if (linear < 0 || !linear)
1287
2
    return linear;
1288
152
1289
152
  return sign < 0;
1290
152
}
1291
1292
/*
1293
 * Set active[i] to 1 if the dimension at position i is involved
1294
 * in the linear expression l.
1295
 */
1296
int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
1297
49.9k
{
1298
49.9k
  int i, j;
1299
49.9k
  isl_ctx *ctx;
1300
49.9k
  int *active = NULL;
1301
49.9k
  unsigned total;
1302
49.9k
  unsigned offset;
1303
49.9k
1304
49.9k
  ctx = isl_local_space_get_ctx(ls);
1305
49.9k
  total = isl_local_space_dim(ls, isl_dim_all);
1306
49.9k
  active = isl_calloc_array(ctx, int, total);
1307
49.9k
  if (total && !active)
1308
0
    return NULL;
1309
49.9k
1310
557k
  
for (i = 0; 49.9k
i < total;
++i507k
)
1311
507k
    active[i] = !isl_int_is_zero(l[i]);
1312
49.9k
1313
49.9k
  offset = isl_local_space_offset(ls, isl_dim_div) - 1;
1314
70.8k
  for (i = ls->div->n_row - 1; i >= 0; 
--i20.8k
) {
1315
20.8k
    if (!active[offset + i])
1316
20.6k
      continue;
1317
1.74k
    
for (j = 0; 198
j < total;
++j1.54k
)
1318
1.54k
      active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
1319
198
  }
1320
49.9k
1321
49.9k
  return active;
1322
49.9k
}
1323
1324
/* Given a local space "ls" of a set, create a local space
1325
 * for the lift of the set.  In particular, the result
1326
 * is of the form [dim -> local[..]], with ls->div->n_row variables in the
1327
 * range of the wrapped map.
1328
 */
1329
__isl_give isl_local_space *isl_local_space_lift(
1330
  __isl_take isl_local_space *ls)
1331
0
{
1332
0
  ls = isl_local_space_cow(ls);
1333
0
  if (!ls)
1334
0
    return NULL;
1335
0
1336
0
  ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
1337
0
  ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
1338
0
  if (!ls->dim || !ls->div)
1339
0
    return isl_local_space_free(ls);
1340
0
1341
0
  return ls;
1342
0
}
1343
1344
/* Construct a basic map that maps a set living in local space "ls"
1345
 * to the corresponding lifted local space.
1346
 */
1347
__isl_give isl_basic_map *isl_local_space_lifting(
1348
  __isl_take isl_local_space *ls)
1349
0
{
1350
0
  isl_basic_map *lifting;
1351
0
  isl_basic_set *bset;
1352
0
1353
0
  if (!ls)
1354
0
    return NULL;
1355
0
  if (!isl_local_space_is_set(ls))
1356
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1357
0
      "lifting only defined on set spaces", goto error);
1358
0
1359
0
  bset = isl_basic_set_from_local_space(ls);
1360
0
  lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
1361
0
  lifting = isl_basic_map_domain_map(lifting);
1362
0
  lifting = isl_basic_map_reverse(lifting);
1363
0
1364
0
  return lifting;
1365
0
error:
1366
0
  isl_local_space_free(ls);
1367
0
  return NULL;
1368
0
}
1369
1370
/* Compute the preimage of "ls" under the function represented by "ma".
1371
 * In other words, plug in "ma" in "ls".  The result is a local space
1372
 * that is part of the domain space of "ma".
1373
 *
1374
 * If the divs in "ls" are represented as
1375
 *
1376
 *  floor((a_i(p) + b_i x + c_i(divs))/n_i)
1377
 *
1378
 * and ma is represented by
1379
 *
1380
 *  x = D(p) + F(y) + G(divs')
1381
 *
1382
 * then the resulting divs are
1383
 *
1384
 *  floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)
1385
 *
1386
 * We first copy over the divs from "ma" and then
1387
 * we add the modified divs from "ls".
1388
 */
1389
__isl_give isl_local_space *isl_local_space_preimage_multi_aff(
1390
  __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma)
1391
17.6k
{
1392
17.6k
  int i;
1393
17.6k
  isl_space *space;
1394
17.6k
  isl_local_space *res = NULL;
1395
17.6k
  int n_div_ls, n_div_ma;
1396
17.6k
  isl_int f, c1, c2, g;
1397
17.6k
1398
17.6k
  ma = isl_multi_aff_align_divs(ma);
1399
17.6k
  if (!ls || !ma)
1400
0
    goto error;
1401
17.6k
  if (!isl_space_is_range_internal(ls->dim, ma->space))
1402
17.6k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
1403
17.6k
      "spaces don't match", goto error);
1404
17.6k
1405
17.6k
  n_div_ls = isl_local_space_dim(ls, isl_dim_div);
1406
17.6k
  n_div_ma = ma->n ? 
isl_aff_dim(ma->u.p[0], isl_dim_div)16.9k
:
0704
;
1407
17.6k
1408
17.6k
  space = isl_space_domain(isl_multi_aff_get_space(ma));
1409
17.6k
  res = isl_local_space_alloc(space, n_div_ma + n_div_ls);
1410
17.6k
  if (!res)
1411
0
    goto error;
1412
17.6k
1413
17.6k
  if (n_div_ma) {
1414
619
    isl_mat_free(res->div);
1415
619
    res->div = isl_mat_copy(ma->u.p[0]->ls->div);
1416
619
    res->div = isl_mat_add_zero_cols(res->div, n_div_ls);
1417
619
    res->div = isl_mat_add_rows(res->div, n_div_ls);
1418
619
    if (!res->div)
1419
0
      goto error;
1420
17.6k
  }
1421
17.6k
1422
17.6k
  isl_int_init(f);
1423
17.6k
  isl_int_init(c1);
1424
17.6k
  isl_int_init(c2);
1425
17.6k
  isl_int_init(g);
1426
17.6k
1427
17.9k
  for (i = 0; i < ls->div->n_row; 
++i304
) {
1428
304
    if (isl_int_is_zero(ls->div->row[i][0])) {
1429
0
      isl_int_set_si(res->div->row[n_div_ma + i][0], 0);
1430
0
      continue;
1431
0
    }
1432
304
    isl_seq_preimage(res->div->row[n_div_ma + i], ls->div->row[i],
1433
304
        ma, 0, 0, n_div_ma, n_div_ls, f, c1, c2, g, 1);
1434
304
    normalize_div(res, n_div_ma + i);
1435
304
  }
1436
17.6k
1437
17.6k
  isl_int_clear(f);
1438
17.6k
  isl_int_clear(c1);
1439
17.6k
  isl_int_clear(c2);
1440
17.6k
  isl_int_clear(g);
1441
17.6k
1442
17.6k
  isl_local_space_free(ls);
1443
17.6k
  isl_multi_aff_free(ma);
1444
17.6k
  return res;
1445
0
error:
1446
0
  isl_local_space_free(ls);
1447
0
  isl_multi_aff_free(ma);
1448
0
  isl_local_space_free(res);
1449
0
  return NULL;
1450
17.6k
}
1451
1452
/* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls"
1453
 * to dimensions of "dst_type" at "dst_pos".
1454
 *
1455
 * Moving to/from local dimensions is not allowed.
1456
 * We currently assume that the dimension type changes.
1457
 */
1458
__isl_give isl_local_space *isl_local_space_move_dims(
1459
  __isl_take isl_local_space *ls,
1460
  enum isl_dim_type dst_type, unsigned dst_pos,
1461
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1462
0
{
1463
0
  unsigned g_dst_pos;
1464
0
  unsigned g_src_pos;
1465
0
1466
0
  if (!ls)
1467
0
    return NULL;
1468
0
  if (n == 0 &&
1469
0
      !isl_local_space_is_named_or_nested(ls, src_type) &&
1470
0
      !isl_local_space_is_named_or_nested(ls, dst_type))
1471
0
    return ls;
1472
0
1473
0
  if (src_pos + n > isl_local_space_dim(ls, src_type))
1474
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1475
0
      "range out of bounds", return isl_local_space_free(ls));
1476
0
  if (dst_pos > isl_local_space_dim(ls, dst_type))
1477
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1478
0
      "position out of bounds",
1479
0
      return isl_local_space_free(ls));
1480
0
  if (src_type == isl_dim_div)
1481
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1482
0
      "cannot move divs", return isl_local_space_free(ls));
1483
0
  if (dst_type == isl_dim_div)
1484
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1485
0
      "cannot move to divs", return isl_local_space_free(ls));
1486
0
  if (dst_type == src_type && dst_pos == src_pos)
1487
0
    return ls;
1488
0
  if (dst_type == src_type)
1489
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1490
0
      "moving dims within the same type not supported",
1491
0
      return isl_local_space_free(ls));
1492
0
1493
0
  ls = isl_local_space_cow(ls);
1494
0
  if (!ls)
1495
0
    return NULL;
1496
0
1497
0
  g_src_pos = 1 + isl_local_space_offset(ls, src_type) + src_pos;
1498
0
  g_dst_pos = 1 + isl_local_space_offset(ls, dst_type) + dst_pos;
1499
0
  if (dst_type > src_type)
1500
0
    g_dst_pos -= n;
1501
0
  ls->div = isl_mat_move_cols(ls->div, g_dst_pos, g_src_pos, n);
1502
0
  if (!ls->div)
1503
0
    return isl_local_space_free(ls);
1504
0
  ls->dim = isl_space_move_dims(ls->dim, dst_type, dst_pos,
1505
0
          src_type, src_pos, n);
1506
0
  if (!ls->dim)
1507
0
    return isl_local_space_free(ls);
1508
0
1509
0
  return ls;
1510
0
}
1511
1512
/* Remove any internal structure of the domain of "ls".
1513
 * If there is any such internal structure in the input,
1514
 * then the name of the corresponding space is also removed.
1515
 */
1516
__isl_give isl_local_space *isl_local_space_flatten_domain(
1517
  __isl_take isl_local_space *ls)
1518
0
{
1519
0
  if (!ls)
1520
0
    return NULL;
1521
0
1522
0
  if (!ls->dim->nested[0])
1523
0
    return ls;
1524
0
1525
0
  ls = isl_local_space_cow(ls);
1526
0
  if (!ls)
1527
0
    return NULL;
1528
0
1529
0
  ls->dim = isl_space_flatten_domain(ls->dim);
1530
0
  if (!ls->dim)
1531
0
    return isl_local_space_free(ls);
1532
0
1533
0
  return ls;
1534
0
}
1535
1536
/* Remove any internal structure of the range of "ls".
1537
 * If there is any such internal structure in the input,
1538
 * then the name of the corresponding space is also removed.
1539
 */
1540
__isl_give isl_local_space *isl_local_space_flatten_range(
1541
  __isl_take isl_local_space *ls)
1542
0
{
1543
0
  if (!ls)
1544
0
    return NULL;
1545
0
1546
0
  if (!ls->dim->nested[1])
1547
0
    return ls;
1548
0
1549
0
  ls = isl_local_space_cow(ls);
1550
0
  if (!ls)
1551
0
    return NULL;
1552
0
1553
0
  ls->dim = isl_space_flatten_range(ls->dim);
1554
0
  if (!ls->dim)
1555
0
    return isl_local_space_free(ls);
1556
0
1557
0
  return ls;
1558
0
}
1559
1560
/* Given the local space "ls" of a map, return the local space of a set
1561
 * that lives in a space that wraps the space of "ls" and that has
1562
 * the same divs.
1563
 */
1564
__isl_give isl_local_space *isl_local_space_wrap(__isl_take isl_local_space *ls)
1565
952
{
1566
952
  ls = isl_local_space_cow(ls);
1567
952
  if (!ls)
1568
0
    return NULL;
1569
952
1570
952
  ls->dim = isl_space_wrap(ls->dim);
1571
952
  if (!ls->dim)
1572
0
    return isl_local_space_free(ls);
1573
952
1574
952
  return ls;
1575
952
}
1576
1577
/* Lift the point "pnt", living in the space of "ls"
1578
 * to live in a space with extra coordinates corresponding
1579
 * to the local variables of "ls".
1580
 */
1581
__isl_give isl_point *isl_local_space_lift_point(__isl_take isl_local_space *ls,
1582
  __isl_take isl_point *pnt)
1583
19
{
1584
19
  unsigned n_local;
1585
19
  isl_space *space;
1586
19
  isl_local *local;
1587
19
  isl_vec *vec;
1588
19
1589
19
  if (isl_local_space_check_has_space(ls, isl_point_peek_space(pnt)) < 0)
1590
0
    goto error;
1591
19
1592
19
  local = isl_local_space_peek_local(ls);
1593
19
  n_local = isl_local_space_dim(ls, isl_dim_div);
1594
19
1595
19
  space = isl_point_take_space(pnt);
1596
19
  vec = isl_point_take_vec(pnt);
1597
19
1598
19
  space = isl_space_lift(space, n_local);
1599
19
  vec = isl_local_extend_point_vec(local, vec);
1600
19
1601
19
  pnt = isl_point_restore_vec(pnt, vec);
1602
19
  pnt = isl_point_restore_space(pnt, space);
1603
19
1604
19
  isl_local_space_free(ls);
1605
19
1606
19
  return pnt;
1607
0
error:
1608
0
  isl_local_space_free(ls);
1609
0
  isl_point_free(pnt);
1610
0
  return NULL;
1611
19
}