Coverage Report

Created: 2018-12-09 11:54

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_coalesce.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 * Copyright 2010      INRIA Saclay
4
 * Copyright 2012-2013 Ecole Normale Superieure
5
 * Copyright 2014      INRIA Rocquencourt
6
 * Copyright 2016      INRIA Paris
7
 *
8
 * Use of this software is governed by the MIT license
9
 *
10
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
11
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
12
 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
13
 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
14
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
15
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
16
 * B.P. 105 - 78153 Le Chesnay, France
17
 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
18
 * CS 42112, 75589 Paris Cedex 12, France
19
 */
20
21
#include <isl_ctx_private.h>
22
#include "isl_map_private.h"
23
#include <isl_seq.h>
24
#include <isl/options.h>
25
#include "isl_tab.h"
26
#include <isl_mat_private.h>
27
#include <isl_local_space_private.h>
28
#include <isl_val_private.h>
29
#include <isl_vec_private.h>
30
#include <isl_aff_private.h>
31
#include <isl_equalities.h>
32
#include <isl_constraint_private.h>
33
34
#include <set_to_map.c>
35
#include <set_from_map.c>
36
37
598k
#define STATUS_ERROR    -1
38
184k
#define STATUS_REDUNDANT   1
39
545k
#define STATUS_VALID     2
40
503k
#define STATUS_SEPARATE    3
41
271k
#define STATUS_CUT     4
42
119k
#define STATUS_ADJ_EQ    5
43
148k
#define STATUS_ADJ_INEQ    6
44
45
static int status_in(isl_int *ineq, struct isl_tab *tab)
46
427k
{
47
427k
  enum isl_ineq_type type = isl_tab_ineq_type(tab, ineq);
48
427k
  switch (type) {
49
427k
  default:
50
0
  case isl_ineq_error:    return STATUS_ERROR;
51
222k
  case isl_ineq_redundant:  return STATUS_VALID;
52
35.8k
  case isl_ineq_separate:   return STATUS_SEPARATE;
53
123k
  case isl_ineq_cut:    return STATUS_CUT;
54
11.5k
  case isl_ineq_adj_eq:   return STATUS_ADJ_EQ;
55
34.1k
  case isl_ineq_adj_ineq:   return STATUS_ADJ_INEQ;
56
427k
  }
57
427k
}
58
59
/* Compute the position of the equalities of basic map "bmap_i"
60
 * with respect to the basic map represented by "tab_j".
61
 * The resulting array has twice as many entries as the number
62
 * of equalities corresponding to the two inequalities to which
63
 * each equality corresponds.
64
 */
65
static int *eq_status_in(__isl_keep isl_basic_map *bmap_i,
66
  struct isl_tab *tab_j)
67
82.3k
{
68
82.3k
  int k, l;
69
82.3k
  int *eq = isl_calloc_array(bmap_i->ctx, int, 2 * bmap_i->n_eq);
70
82.3k
  unsigned dim;
71
82.3k
72
82.3k
  if (!eq)
73
0
    return NULL;
74
82.3k
75
82.3k
  dim = isl_basic_map_total_dim(bmap_i);
76
145k
  for (k = 0; k < bmap_i->n_eq; 
++k63.0k
) {
77
189k
    for (l = 0; l < 2; 
++l126k
) {
78
126k
      isl_seq_neg(bmap_i->eq[k], bmap_i->eq[k], 1+dim);
79
126k
      eq[2 * k + l] = status_in(bmap_i->eq[k], tab_j);
80
126k
      if (eq[2 * k + l] == STATUS_ERROR)
81
126k
        
goto error0
;
82
126k
    }
83
63.0k
  }
84
82.3k
85
82.3k
  return eq;
86
0
error:
87
0
  free(eq);
88
0
  return NULL;
89
82.3k
}
90
91
/* Compute the position of the inequalities of basic map "bmap_i"
92
 * (also represented by "tab_i", if not NULL) with respect to the basic map
93
 * represented by "tab_j".
94
 */
95
static int *ineq_status_in(__isl_keep isl_basic_map *bmap_i,
96
  struct isl_tab *tab_i, struct isl_tab *tab_j)
97
108k
{
98
108k
  int k;
99
108k
  unsigned n_eq = bmap_i->n_eq;
100
108k
  int *ineq = isl_calloc_array(bmap_i->ctx, int, bmap_i->n_ineq);
101
108k
102
108k
  if (!ineq)
103
0
    return NULL;
104
108k
105
371k
  
for (k = 0; 108k
k < bmap_i->n_ineq;
++k262k
) {
106
287k
    if (tab_i && 
isl_tab_is_redundant(tab_i, n_eq + k)267k
) {
107
11.4k
      ineq[k] = STATUS_REDUNDANT;
108
11.4k
      continue;
109
11.4k
    }
110
275k
    ineq[k] = status_in(bmap_i->ineq[k], tab_j);
111
275k
    if (ineq[k] == STATUS_ERROR)
112
275k
      
goto error0
;
113
275k
    if (ineq[k] == STATUS_SEPARATE)
114
275k
      
break25.2k
;
115
275k
  }
116
108k
117
108k
  return ineq;
118
0
error:
119
0
  free(ineq);
120
0
  return NULL;
121
108k
}
122
123
static int any(int *con, unsigned len, int status)
124
643k
{
125
643k
  int i;
126
643k
127
1.85M
  for (i = 0; i < len ; 
++i1.21M
)
128
1.28M
    if (con[i] == status)
129
64.2k
      return 1;
130
643k
  
return 0578k
;
131
643k
}
132
133
/* Return the first position of "status" in the list "con" of length "len".
134
 * Return -1 if there is no such entry.
135
 */
136
static int find(int *con, unsigned len, int status)
137
4.94k
{
138
4.94k
  int i;
139
4.94k
140
14.5k
  for (i = 0; i < len ; 
++i9.61k
)
141
14.5k
    if (con[i] == status)
142
4.94k
      return i;
143
4.94k
  
return -10
;
144
4.94k
}
145
146
static int count(int *con, unsigned len, int status)
147
67.3k
{
148
67.3k
  int i;
149
67.3k
  int c = 0;
150
67.3k
151
240k
  for (i = 0; i < len ; 
++i173k
)
152
173k
    if (con[i] == status)
153
56.5k
      c++;
154
67.3k
  return c;
155
67.3k
}
156
157
static int all(int *con, unsigned len, int status)
158
124k
{
159
124k
  int i;
160
124k
161
200k
  for (i = 0; i < len ; 
++i76.3k
) {
162
141k
    if (con[i] == STATUS_REDUNDANT)
163
141k
      
continue1.69k
;
164
140k
    if (con[i] != status)
165
65.5k
      return 0;
166
140k
  }
167
124k
  
return 158.9k
;
168
124k
}
169
170
/* Internal information associated to a basic map in a map
171
 * that is to be coalesced by isl_map_coalesce.
172
 *
173
 * "bmap" is the basic map itself (or NULL if "removed" is set)
174
 * "tab" is the corresponding tableau (or NULL if "removed" is set)
175
 * "hull_hash" identifies the affine space in which "bmap" lives.
176
 * "removed" is set if this basic map has been removed from the map
177
 * "simplify" is set if this basic map may have some unknown integer
178
 * divisions that were not present in the input basic maps.  The basic
179
 * map should then be simplified such that we may be able to find
180
 * a definition among the constraints.
181
 *
182
 * "eq" and "ineq" are only set if we are currently trying to coalesce
183
 * this basic map with another basic map, in which case they represent
184
 * the position of the inequalities of this basic map with respect to
185
 * the other basic map.  The number of elements in the "eq" array
186
 * is twice the number of equalities in the "bmap", corresponding
187
 * to the two inequalities that make up each equality.
188
 */
189
struct isl_coalesce_info {
190
  isl_basic_map *bmap;
191
  struct isl_tab *tab;
192
  uint32_t hull_hash;
193
  int removed;
194
  int simplify;
195
  int *eq;
196
  int *ineq;
197
};
198
199
/* Is there any (half of an) equality constraint in the description
200
 * of the basic map represented by "info" that
201
 * has position "status" with respect to the other basic map?
202
 */
203
static int any_eq(struct isl_coalesce_info *info, int status)
204
314k
{
205
314k
  unsigned n_eq;
206
314k
207
314k
  n_eq = isl_basic_map_n_equality(info->bmap);
208
314k
  return any(info->eq, 2 * n_eq, status);
209
314k
}
210
211
/* Is there any inequality constraint in the description
212
 * of the basic map represented by "info" that
213
 * has position "status" with respect to the other basic map?
214
 */
215
static int any_ineq(struct isl_coalesce_info *info, int status)
216
320k
{
217
320k
  unsigned n_ineq;
218
320k
219
320k
  n_ineq = isl_basic_map_n_inequality(info->bmap);
220
320k
  return any(info->ineq, n_ineq, status);
221
320k
}
222
223
/* Return the position of the first half on an equality constraint
224
 * in the description of the basic map represented by "info" that
225
 * has position "status" with respect to the other basic map.
226
 * The returned value is twice the position of the equality constraint
227
 * plus zero for the negative half and plus one for the positive half.
228
 * Return -1 if there is no such entry.
229
 */
230
static int find_eq(struct isl_coalesce_info *info, int status)
231
2.08k
{
232
2.08k
  unsigned n_eq;
233
2.08k
234
2.08k
  n_eq = isl_basic_map_n_equality(info->bmap);
235
2.08k
  return find(info->eq, 2 * n_eq, status);
236
2.08k
}
237
238
/* Return the position of the first inequality constraint in the description
239
 * of the basic map represented by "info" that
240
 * has position "status" with respect to the other basic map.
241
 * Return -1 if there is no such entry.
242
 */
243
static int find_ineq(struct isl_coalesce_info *info, int status)
244
2.86k
{
245
2.86k
  unsigned n_ineq;
246
2.86k
247
2.86k
  n_ineq = isl_basic_map_n_inequality(info->bmap);
248
2.86k
  return find(info->ineq, n_ineq, status);
249
2.86k
}
250
251
/* Return the number of (halves of) equality constraints in the description
252
 * of the basic map represented by "info" that
253
 * have position "status" with respect to the other basic map.
254
 */
255
static int count_eq(struct isl_coalesce_info *info, int status)
256
23.5k
{
257
23.5k
  unsigned n_eq;
258
23.5k
259
23.5k
  n_eq = isl_basic_map_n_equality(info->bmap);
260
23.5k
  return count(info->eq, 2 * n_eq, status);
261
23.5k
}
262
263
/* Return the number of inequality constraints in the description
264
 * of the basic map represented by "info" that
265
 * have position "status" with respect to the other basic map.
266
 */
267
static int count_ineq(struct isl_coalesce_info *info, int status)
268
43.7k
{
269
43.7k
  unsigned n_ineq;
270
43.7k
271
43.7k
  n_ineq = isl_basic_map_n_inequality(info->bmap);
272
43.7k
  return count(info->ineq, n_ineq, status);
273
43.7k
}
274
275
/* Are all non-redundant constraints of the basic map represented by "info"
276
 * either valid or cut constraints with respect to the other basic map?
277
 */
278
static int all_valid_or_cut(struct isl_coalesce_info *info)
279
493
{
280
493
  int i;
281
493
282
2.58k
  for (i = 0; i < 2 * info->bmap->n_eq; 
++i2.09k
) {
283
2.09k
    if (info->eq[i] == STATUS_REDUNDANT)
284
2.09k
      
continue0
;
285
2.09k
    if (info->eq[i] == STATUS_VALID)
286
2.09k
      
continue1.50k
;
287
591
    if (info->eq[i] == STATUS_CUT)
288
591
      continue;
289
0
    return 0;
290
0
  }
291
493
292
1.14k
  
for (i = 0; 493
i < info->bmap->n_ineq;
++i653
) {
293
1.09k
    if (info->ineq[i] == STATUS_REDUNDANT)
294
1.09k
      
continue24
;
295
1.07k
    if (info->ineq[i] == STATUS_VALID)
296
1.07k
      
continue535
;
297
540
    if (info->ineq[i] == STATUS_CUT)
298
540
      
continue94
;
299
446
    return 0;
300
446
  }
301
493
302
493
  
return 147
;
303
493
}
304
305
/* Compute the hash of the (apparent) affine hull of info->bmap (with
306
 * the existentially quantified variables removed) and store it
307
 * in info->hash.
308
 */
309
static int coalesce_info_set_hull_hash(struct isl_coalesce_info *info)
310
58.4k
{
311
58.4k
  isl_basic_map *hull;
312
58.4k
  unsigned n_div;
313
58.4k
314
58.4k
  hull = isl_basic_map_copy(info->bmap);
315
58.4k
  hull = isl_basic_map_plain_affine_hull(hull);
316
58.4k
  n_div = isl_basic_map_dim(hull, isl_dim_div);
317
58.4k
  hull = isl_basic_map_drop_constraints_involving_dims(hull,
318
58.4k
              isl_dim_div, 0, n_div);
319
58.4k
  info->hull_hash = isl_basic_map_get_hash(hull);
320
58.4k
  isl_basic_map_free(hull);
321
58.4k
322
58.4k
  return hull ? 0 : 
-10
;
323
58.4k
}
324
325
/* Free all the allocated memory in an array
326
 * of "n" isl_coalesce_info elements.
327
 */
328
static void clear_coalesce_info(int n, struct isl_coalesce_info *info)
329
24.3k
{
330
24.3k
  int i;
331
24.3k
332
24.3k
  if (!info)
333
0
    return;
334
24.3k
335
82.8k
  
for (i = 0; 24.3k
i < n;
++i58.4k
) {
336
58.4k
    isl_basic_map_free(info[i].bmap);
337
58.4k
    isl_tab_free(info[i].tab);
338
58.4k
  }
339
24.3k
340
24.3k
  free(info);
341
24.3k
}
342
343
/* Drop the basic map represented by "info".
344
 * That is, clear the memory associated to the entry and
345
 * mark it as having been removed.
346
 */
347
static void drop(struct isl_coalesce_info *info)
348
10.2k
{
349
10.2k
  info->bmap = isl_basic_map_free(info->bmap);
350
10.2k
  isl_tab_free(info->tab);
351
10.2k
  info->tab = NULL;
352
10.2k
  info->removed = 1;
353
10.2k
}
354
355
/* Exchange the information in "info1" with that in "info2".
356
 */
357
static void exchange(struct isl_coalesce_info *info1,
358
  struct isl_coalesce_info *info2)
359
260
{
360
260
  struct isl_coalesce_info info;
361
260
362
260
  info = *info1;
363
260
  *info1 = *info2;
364
260
  *info2 = info;
365
260
}
366
367
/* This type represents the kind of change that has been performed
368
 * while trying to coalesce two basic maps.
369
 *
370
 * isl_change_none: nothing was changed
371
 * isl_change_drop_first: the first basic map was removed
372
 * isl_change_drop_second: the second basic map was removed
373
 * isl_change_fuse: the two basic maps were replaced by a new basic map.
374
 */
375
enum isl_change {
376
  isl_change_error = -1,
377
  isl_change_none = 0,
378
  isl_change_drop_first,
379
  isl_change_drop_second,
380
  isl_change_fuse,
381
};
382
383
/* Update "change" based on an interchange of the first and the second
384
 * basic map.  That is, interchange isl_change_drop_first and
385
 * isl_change_drop_second.
386
 */
387
static enum isl_change invert_change(enum isl_change change)
388
63
{
389
63
  switch (change) {
390
63
  case isl_change_error:
391
0
    return isl_change_error;
392
63
  case isl_change_none:
393
0
    return isl_change_none;
394
63
  case isl_change_drop_first:
395
4
    return isl_change_drop_second;
396
63
  case isl_change_drop_second:
397
17
    return isl_change_drop_first;
398
63
  case isl_change_fuse:
399
42
    return isl_change_fuse;
400
0
  }
401
0
402
0
  return isl_change_error;
403
0
}
404
405
/* Add the valid constraints of the basic map represented by "info"
406
 * to "bmap".  "len" is the size of the constraints.
407
 * If only one of the pair of inequalities that make up an equality
408
 * is valid, then add that inequality.
409
 */
410
static __isl_give isl_basic_map *add_valid_constraints(
411
  __isl_take isl_basic_map *bmap, struct isl_coalesce_info *info,
412
  unsigned len)
413
2.52k
{
414
2.52k
  int k, l;
415
2.52k
416
2.52k
  if (!bmap)
417
0
    return NULL;
418
2.52k
419
6.51k
  
for (k = 0; 2.52k
k < info->bmap->n_eq;
++k3.99k
) {
420
3.99k
    if (info->eq[2 * k] == STATUS_VALID &&
421
3.99k
        
info->eq[2 * k + 1] == 2.99k
STATUS_VALID2.99k
) {
422
2.06k
      l = isl_basic_map_alloc_equality(bmap);
423
2.06k
      if (l < 0)
424
0
        return isl_basic_map_free(bmap);
425
2.06k
      isl_seq_cpy(bmap->eq[l], info->bmap->eq[k], len);
426
2.06k
    } else 
if (1.92k
info->eq[2 * k] == 1.92k
STATUS_VALID1.92k
) {
427
930
      l = isl_basic_map_alloc_inequality(bmap);
428
930
      if (l < 0)
429
0
        return isl_basic_map_free(bmap);
430
930
      isl_seq_neg(bmap->ineq[l], info->bmap->eq[k], len);
431
995
    } else if (info->eq[2 * k + 1] == STATUS_VALID) {
432
989
      l = isl_basic_map_alloc_inequality(bmap);
433
989
      if (l < 0)
434
0
        return isl_basic_map_free(bmap);
435
989
      isl_seq_cpy(bmap->ineq[l], info->bmap->eq[k], len);
436
989
    }
437
3.99k
  }
438
2.52k
439
9.28k
  
for (k = 0; 2.52k
k < info->bmap->n_ineq;
++k6.75k
) {
440
6.75k
    if (info->ineq[k] != STATUS_VALID)
441
6.75k
      
continue2.10k
;
442
4.65k
    l = isl_basic_map_alloc_inequality(bmap);
443
4.65k
    if (l < 0)
444
0
      return isl_basic_map_free(bmap);
445
4.65k
    isl_seq_cpy(bmap->ineq[l], info->bmap->ineq[k], len);
446
4.65k
  }
447
2.52k
448
2.52k
  return bmap;
449
2.52k
}
450
451
/* Is "bmap" defined by a number of (non-redundant) constraints that
452
 * is greater than the number of constraints of basic maps i and j combined?
453
 * Equalities are counted as two inequalities.
454
 */
455
static int number_of_constraints_increases(int i, int j,
456
  struct isl_coalesce_info *info,
457
  __isl_keep isl_basic_map *bmap, struct isl_tab *tab)
458
32
{
459
32
  int k, n_old, n_new;
460
32
461
32
  n_old = 2 * info[i].bmap->n_eq + info[i].bmap->n_ineq;
462
32
  n_old += 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq;
463
32
464
32
  n_new = 2 * bmap->n_eq;
465
290
  for (k = 0; k < bmap->n_ineq; 
++k258
)
466
258
    if (!isl_tab_is_redundant(tab, bmap->n_eq + k))
467
141
      ++n_new;
468
32
469
32
  return n_new > n_old;
470
32
}
471
472
/* Replace the pair of basic maps i and j by the basic map bounded
473
 * by the valid constraints in both basic maps and the constraints
474
 * in extra (if not NULL).
475
 * Place the fused basic map in the position that is the smallest of i and j.
476
 *
477
 * If "detect_equalities" is set, then look for equalities encoded
478
 * as pairs of inequalities.
479
 * If "check_number" is set, then the original basic maps are only
480
 * replaced if the total number of constraints does not increase.
481
 * While the number of integer divisions in the two basic maps
482
 * is assumed to be the same, the actual definitions may be different.
483
 * We only copy the definition from one of the basic map if it is
484
 * the same as that of the other basic map.  Otherwise, we mark
485
 * the integer division as unknown and simplify the basic map
486
 * in an attempt to recover the integer division definition.
487
 */
488
static enum isl_change fuse(int i, int j, struct isl_coalesce_info *info,
489
  __isl_keep isl_mat *extra, int detect_equalities, int check_number)
490
1.31k
{
491
1.31k
  int k, l;
492
1.31k
  struct isl_basic_map *fused = NULL;
493
1.31k
  struct isl_tab *fused_tab = NULL;
494
1.31k
  unsigned total = isl_basic_map_total_dim(info[i].bmap);
495
1.31k
  unsigned extra_rows = extra ? 
extra->n_row666
:
0649
;
496
1.31k
  unsigned n_eq, n_ineq;
497
1.31k
  int simplify = 0;
498
1.31k
499
1.31k
  if (j < i)
500
54
    return fuse(j, i, info, extra, detect_equalities, check_number);
501
1.26k
502
1.26k
  n_eq = info[i].bmap->n_eq + info[j].bmap->n_eq;
503
1.26k
  n_ineq = info[i].bmap->n_ineq + info[j].bmap->n_ineq;
504
1.26k
  fused = isl_basic_map_alloc_space(isl_space_copy(info[i].bmap->dim),
505
1.26k
        info[i].bmap->n_div, n_eq, n_eq + n_ineq + extra_rows);
506
1.26k
  fused = add_valid_constraints(fused, &info[i], 1 + total);
507
1.26k
  fused = add_valid_constraints(fused, &info[j], 1 + total);
508
1.26k
  if (!fused)
509
0
    goto error;
510
1.26k
  if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) &&
511
1.26k
      
ISL_F_ISSET0
(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
512
1.26k
    ISL_F_SET(fused, ISL_BASIC_MAP_RATIONAL);
513
1.26k
514
1.38k
  for (k = 0; k < info[i].bmap->n_div; 
++k125
) {
515
125
    int l = isl_basic_map_alloc_div(fused);
516
125
    if (l < 0)
517
0
      goto error;
518
125
    if (isl_seq_eq(info[i].bmap->div[k], info[j].bmap->div[k],
519
125
        1 + 1 + total)) {
520
125
      isl_seq_cpy(fused->div[l], info[i].bmap->div[k],
521
125
        1 + 1 + total);
522
125
    } else {
523
0
      isl_int_set_si(fused->div[l][0], 0);
524
0
      simplify = 1;
525
0
    }
526
125
  }
527
1.26k
528
3.35k
  
for (k = 0; 1.26k
k < extra_rows;
++k2.09k
) {
529
2.09k
    l = isl_basic_map_alloc_inequality(fused);
530
2.09k
    if (l < 0)
531
0
      goto error;
532
2.09k
    isl_seq_cpy(fused->ineq[l], extra->row[k], 1 + total);
533
2.09k
  }
534
1.26k
535
1.26k
  if (detect_equalities)
536
313
    fused = isl_basic_map_detect_inequality_pairs(fused, NULL);
537
1.26k
  fused = isl_basic_map_gauss(fused, NULL);
538
1.26k
  if (simplify || info[j].simplify) {
539
0
    fused = isl_basic_map_simplify(fused);
540
0
    info[i].simplify = 0;
541
0
  }
542
1.26k
  fused = isl_basic_map_finalize(fused);
543
1.26k
544
1.26k
  fused_tab = isl_tab_from_basic_map(fused, 0);
545
1.26k
  if (isl_tab_detect_redundant(fused_tab) < 0)
546
0
    goto error;
547
1.26k
548
1.26k
  if (check_number &&
549
1.26k
      
number_of_constraints_increases(i, j, info, fused, fused_tab)32
) {
550
0
    isl_tab_free(fused_tab);
551
0
    isl_basic_map_free(fused);
552
0
    return isl_change_none;
553
0
  }
554
1.26k
555
1.26k
  isl_basic_map_free(info[i].bmap);
556
1.26k
  info[i].bmap = fused;
557
1.26k
  isl_tab_free(info[i].tab);
558
1.26k
  info[i].tab = fused_tab;
559
1.26k
  drop(&info[j]);
560
1.26k
561
1.26k
  return isl_change_fuse;
562
0
error:
563
0
  isl_tab_free(fused_tab);
564
0
  isl_basic_map_free(fused);
565
0
  return isl_change_error;
566
1.26k
}
567
568
/* Given a pair of basic maps i and j such that all constraints are either
569
 * "valid" or "cut", check if the facets corresponding to the "cut"
570
 * constraints of i lie entirely within basic map j.
571
 * If so, replace the pair by the basic map consisting of the valid
572
 * constraints in both basic maps.
573
 * Checking whether the facet lies entirely within basic map j
574
 * is performed by checking whether the constraints of basic map j
575
 * are valid for the facet.  These tests are performed on a rational
576
 * tableau to avoid the theoretical possibility that a constraint
577
 * that was considered to be a cut constraint for the entire basic map i
578
 * happens to be considered to be a valid constraint for the facet,
579
 * even though it cuts off the same rational points.
580
 *
581
 * To see that we are not introducing any extra points, call the
582
 * two basic maps A and B and the resulting map U and let x
583
 * be an element of U \setminus ( A \cup B ).
584
 * A line connecting x with an element of A \cup B meets a facet F
585
 * of either A or B.  Assume it is a facet of B and let c_1 be
586
 * the corresponding facet constraint.  We have c_1(x) < 0 and
587
 * so c_1 is a cut constraint.  This implies that there is some
588
 * (possibly rational) point x' satisfying the constraints of A
589
 * and the opposite of c_1 as otherwise c_1 would have been marked
590
 * valid for A.  The line connecting x and x' meets a facet of A
591
 * in a (possibly rational) point that also violates c_1, but this
592
 * is impossible since all cut constraints of B are valid for all
593
 * cut facets of A.
594
 * In case F is a facet of A rather than B, then we can apply the
595
 * above reasoning to find a facet of B separating x from A \cup B first.
596
 */
597
static enum isl_change check_facets(int i, int j,
598
  struct isl_coalesce_info *info)
599
9.50k
{
600
9.50k
  int k, l;
601
9.50k
  struct isl_tab_undo *snap, *snap2;
602
9.50k
  unsigned n_eq = info[i].bmap->n_eq;
603
9.50k
604
9.50k
  snap = isl_tab_snap(info[i].tab);
605
9.50k
  if (isl_tab_mark_rational(info[i].tab) < 0)
606
0
    return isl_change_error;
607
9.50k
  snap2 = isl_tab_snap(info[i].tab);
608
9.50k
609
10.8k
  for (k = 0; k < info[i].bmap->n_ineq; 
++k1.33k
) {
610
10.8k
    if (info[i].ineq[k] != STATUS_CUT)
611
10.8k
      
continue1.29k
;
612
9.51k
    if (isl_tab_select_facet(info[i].tab, n_eq + k) < 0)
613
0
      return isl_change_error;
614
11.0k
    
for (l = 0; 9.51k
l < info[j].bmap->n_ineq;
++l1.52k
) {
615
10.9k
      int stat;
616
10.9k
      if (info[j].ineq[l] != STATUS_CUT)
617
10.9k
        
continue1.46k
;
618
9.51k
      stat = status_in(info[j].bmap->ineq[l], info[i].tab);
619
9.51k
      if (stat < 0)
620
0
        return isl_change_error;
621
9.51k
      if (stat != STATUS_VALID)
622
9.51k
        
break9.46k
;
623
9.51k
    }
624
9.51k
    if (isl_tab_rollback(info[i].tab, snap2) < 0)
625
0
      return isl_change_error;
626
9.51k
    if (l < info[j].bmap->n_ineq)
627
9.46k
      break;
628
9.51k
  }
629
9.50k
630
9.50k
  if (k < info[i].bmap->n_ineq) {
631
9.46k
    if (isl_tab_rollback(info[i].tab, snap) < 0)
632
0
      return isl_change_error;
633
9.46k
    return isl_change_none;
634
9.46k
  }
635
37
  return fuse(i, j, info, NULL, 0, 0);
636
37
}
637
638
/* Check if info->bmap contains the basic map represented
639
 * by the tableau "tab".
640
 * For each equality, we check both the constraint itself
641
 * (as an inequality) and its negation.  Make sure the
642
 * equality is returned to its original state before returning.
643
 */
644
static isl_bool contains(struct isl_coalesce_info *info, struct isl_tab *tab)
645
2.43k
{
646
2.43k
  int k;
647
2.43k
  unsigned dim;
648
2.43k
  isl_basic_map *bmap = info->bmap;
649
2.43k
650
2.43k
  dim = isl_basic_map_total_dim(bmap);
651
7.24k
  for (k = 0; k < bmap->n_eq; 
++k4.81k
) {
652
5.34k
    int stat;
653
5.34k
    isl_seq_neg(bmap->eq[k], bmap->eq[k], 1 + dim);
654
5.34k
    stat = status_in(bmap->eq[k], tab);
655
5.34k
    isl_seq_neg(bmap->eq[k], bmap->eq[k], 1 + dim);
656
5.34k
    if (stat < 0)
657
0
      return isl_bool_error;
658
5.34k
    if (stat != STATUS_VALID)
659
5.34k
      
return isl_bool_false484
;
660
4.85k
    stat = status_in(bmap->eq[k], tab);
661
4.85k
    if (stat < 0)
662
0
      return isl_bool_error;
663
4.85k
    if (stat != STATUS_VALID)
664
4.85k
      
return isl_bool_false45
;
665
4.85k
  }
666
2.43k
667
6.23k
  
for (k = 0; 1.90k
k < bmap->n_ineq;
++k4.32k
) {
668
5.62k
    int stat;
669
5.62k
    if (info->ineq[k] == STATUS_REDUNDANT)
670
5.62k
      
continue325
;
671
5.29k
    stat = status_in(bmap->ineq[k], tab);
672
5.29k
    if (stat < 0)
673
0
      return isl_bool_error;
674
5.29k
    if (stat != STATUS_VALID)
675
5.29k
      
return isl_bool_false1.29k
;
676
5.29k
  }
677
1.90k
  
return isl_bool_true610
;
678
1.90k
}
679
680
/* Basic map "i" has an inequality (say "k") that is adjacent
681
 * to some inequality of basic map "j".  All the other inequalities
682
 * are valid for "j".
683
 * Check if basic map "j" forms an extension of basic map "i".
684
 *
685
 * Note that this function is only called if some of the equalities or
686
 * inequalities of basic map "j" do cut basic map "i".  The function is
687
 * correct even if there are no such cut constraints, but in that case
688
 * the additional checks performed by this function are overkill.
689
 *
690
 * In particular, we replace constraint k, say f >= 0, by constraint
691
 * f <= -1, add the inequalities of "j" that are valid for "i"
692
 * and check if the result is a subset of basic map "j".
693
 * To improve the chances of the subset relation being detected,
694
 * any variable that only attains a single integer value
695
 * in the tableau of "i" is first fixed to that value.
696
 * If the result is a subset, then we know that this result is exactly equal
697
 * to basic map "j" since all its constraints are valid for basic map "j".
698
 * By combining the valid constraints of "i" (all equalities and all
699
 * inequalities except "k") and the valid constraints of "j" we therefore
700
 * obtain a basic map that is equal to their union.
701
 * In this case, there is no need to perform a rollback of the tableau
702
 * since it is going to be destroyed in fuse().
703
 *
704
 *
705
 *  |\__      |\__
706
 *  |   \__     |   \__
707
 *  |      \_ =>  |      \__
708
 *  |_______| _   |_________\
709
 *
710
 *
711
 *  |\      |\
712
 *  | \     | \
713
 *  |  \      |  \
714
 *  |  |      |   \
715
 *  |  ||\    =>      |    \
716
 *  |  || \     |     \
717
 *  |  ||  |    |      |
718
 *  |__||_/     |_____/
719
 */
720
static enum isl_change is_adj_ineq_extension(int i, int j,
721
  struct isl_coalesce_info *info)
722
531
{
723
531
  int k;
724
531
  struct isl_tab_undo *snap;
725
531
  unsigned n_eq = info[i].bmap->n_eq;
726
531
  unsigned total = isl_basic_map_total_dim(info[i].bmap);
727
531
  isl_stat r;
728
531
  isl_bool super;
729
531
730
531
  if (isl_tab_extend_cons(info[i].tab, 1 + info[j].bmap->n_ineq) < 0)
731
0
    return isl_change_error;
732
531
733
531
  k = find_ineq(&info[i], STATUS_ADJ_INEQ);
734
531
  if (k < 0)
735
531
    
isl_die0
(isl_basic_map_get_ctx(info[i].bmap), isl_error_internal,
736
531
      "info[i].ineq should have exactly one STATUS_ADJ_INEQ",
737
531
      return isl_change_error);
738
531
739
531
  snap = isl_tab_snap(info[i].tab);
740
531
741
531
  if (isl_tab_unrestrict(info[i].tab, n_eq + k) < 0)
742
0
    return isl_change_error;
743
531
744
531
  isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total);
745
531
  isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1);
746
531
  r = isl_tab_add_ineq(info[i].tab, info[i].bmap->ineq[k]);
747
531
  isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total);
748
531
  isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1);
749
531
  if (r < 0)
750
0
    return isl_change_error;
751
531
752
2.99k
  
for (k = 0; 531
k < info[j].bmap->n_ineq;
++k2.46k
) {
753
2.46k
    if (info[j].ineq[k] != STATUS_VALID)
754
2.46k
      
continue1.20k
;
755
1.26k
    if (isl_tab_add_ineq(info[i].tab, info[j].bmap->ineq[k]) < 0)
756
0
      return isl_change_error;
757
1.26k
  }
758
531
  if (isl_tab_detect_constants(info[i].tab) < 0)
759
0
    return isl_change_error;
760
531
761
531
  super = contains(&info[j], info[i].tab);
762
531
  if (super < 0)
763
0
    return isl_change_error;
764
531
  if (super)
765
27
    return fuse(i, j, info, NULL, 0, 0);
766
504
767
504
  if (isl_tab_rollback(info[i].tab, snap) < 0)
768
0
    return isl_change_error;
769
504
770
504
  return isl_change_none;
771
504
}
772
773
774
/* Both basic maps have at least one inequality with and adjacent
775
 * (but opposite) inequality in the other basic map.
776
 * Check that there are no cut constraints and that there is only
777
 * a single pair of adjacent inequalities.
778
 * If so, we can replace the pair by a single basic map described
779
 * by all but the pair of adjacent inequalities.
780
 * Any additional points introduced lie strictly between the two
781
 * adjacent hyperplanes and can therefore be integral.
782
 *
783
 *        ____        _____
784
 *       /    ||\    /     \
785
 *      /     || \    /       \
786
 *      \     ||  \ =>  \        \
787
 *       \    ||  /    \       /
788
 *        \___||_/      \_____/
789
 *
790
 * The test for a single pair of adjancent inequalities is important
791
 * for avoiding the combination of two basic maps like the following
792
 *
793
 *       /|
794
 *      / |
795
 *     /__|
796
 *         _____
797
 *         |   |
798
 *         |   |
799
 *         |___|
800
 *
801
 * If there are some cut constraints on one side, then we may
802
 * still be able to fuse the two basic maps, but we need to perform
803
 * some additional checks in is_adj_ineq_extension.
804
 */
805
static enum isl_change check_adj_ineq(int i, int j,
806
  struct isl_coalesce_info *info)
807
8.41k
{
808
8.41k
  int count_i, count_j;
809
8.41k
  int cut_i, cut_j;
810
8.41k
811
8.41k
  count_i = count_ineq(&info[i], STATUS_ADJ_INEQ);
812
8.41k
  count_j = count_ineq(&info[j], STATUS_ADJ_INEQ);
813
8.41k
814
8.41k
  if (count_i != 1 && 
count_j != 11.88k
)
815
1.85k
    return isl_change_none;
816
6.56k
817
6.56k
  cut_i = any_eq(&info[i], STATUS_CUT) || 
any_ineq(&info[i], 6.43k
STATUS_CUT6.43k
);
818
6.56k
  cut_j = any_eq(&info[j], STATUS_CUT) || 
any_ineq(&info[j], 6.39k
STATUS_CUT6.39k
);
819
6.56k
820
6.56k
  if (!cut_i && 
!cut_j976
&&
count_i == 1572
&&
count_j == 1572
)
821
572
    return fuse(i, j, info, NULL, 0, 0);
822
5.98k
823
5.98k
  if (count_i == 1 && 
!cut_i5.95k
)
824
399
    return is_adj_ineq_extension(i, j, info);
825
5.58k
826
5.58k
  if (count_j == 1 && 
!cut_j5.56k
)
827
121
    return is_adj_ineq_extension(j, i, info);
828
5.46k
829
5.46k
  return isl_change_none;
830
5.46k
}
831
832
/* Given an affine transformation matrix "T", does row "row" represent
833
 * anything other than a unit vector (possibly shifted by a constant)
834
 * that is not involved in any of the other rows?
835
 *
836
 * That is, if a constraint involves the variable corresponding to
837
 * the row, then could its preimage by "T" have any coefficients
838
 * that are different from those in the original constraint?
839
 */
840
static int not_unique_unit_row(__isl_keep isl_mat *T, int row)
841
10.4k
{
842
10.4k
  int i, j;
843
10.4k
  int len = T->n_col - 1;
844
10.4k
845
10.4k
  i = isl_seq_first_non_zero(T->row[row] + 1, len);
846
10.4k
  if (i < 0)
847
1.44k
    return 1;
848
9.02k
  if (!isl_int_is_one(T->row[row][1 + i]) &&
849
9.02k
      
!129
isl_int_is_negone129
(T->row[row][1 + i]))
850
9.02k
    
return 1112
;
851
8.91k
852
8.91k
  j = isl_seq_first_non_zero(T->row[row] + 1 + i + 1, len - (i + 1));
853
8.91k
  if (j >= 0)
854
8
    return 1;
855
8.90k
856
64.8k
  
for (j = 1; 8.90k
j < T->n_row;
++j55.9k
) {
857
56.7k
    if (j == row)
858
8.47k
      continue;
859
48.3k
    if (!isl_int_is_zero(T->row[j][1 + i]))
860
48.3k
      
return 1833
;
861
48.3k
  }
862
8.90k
863
8.90k
  
return 08.06k
;
864
8.90k
}
865
866
/* Does inequality constraint "ineq" of "bmap" involve any of
867
 * the variables marked in "affected"?
868
 * "total" is the total number of variables, i.e., the number
869
 * of entries in "affected".
870
 */
871
static isl_bool is_affected(__isl_keep isl_basic_map *bmap, int ineq,
872
  int *affected, int total)
873
5.09k
{
874
5.09k
  int i;
875
5.09k
876
32.8k
  for (i = 0; i < total; 
++i27.7k
) {
877
29.2k
    if (!affected[i])
878
23.6k
      continue;
879
5.52k
    if (!isl_int_is_zero(bmap->ineq[ineq][1 + i]))
880
5.52k
      
return isl_bool_true1.50k
;
881
5.52k
  }
882
5.09k
883
5.09k
  
return isl_bool_false3.59k
;
884
5.09k
}
885
886
/* Given the compressed version of inequality constraint "ineq"
887
 * of info->bmap in "v", check if the constraint can be tightened,
888
 * where the compression is based on an equality constraint valid
889
 * for info->tab.
890
 * If so, add the tightened version of the inequality constraint
891
 * to info->tab.  "v" may be modified by this function.
892
 *
893
 * That is, if the compressed constraint is of the form
894
 *
895
 *  m f() + c >= 0
896
 *
897
 * with 0 < c < m, then it is equivalent to
898
 *
899
 *  f() >= 0
900
 *
901
 * This means that c can also be subtracted from the original,
902
 * uncompressed constraint without affecting the integer points
903
 * in info->tab.  Add this tightened constraint as an extra row
904
 * to info->tab to make this information explicitly available.
905
 */
906
static __isl_give isl_vec *try_tightening(struct isl_coalesce_info *info,
907
  int ineq, __isl_take isl_vec *v)
908
1.50k
{
909
1.50k
  isl_ctx *ctx;
910
1.50k
  isl_stat r;
911
1.50k
912
1.50k
  if (!v)
913
0
    return NULL;
914
1.50k
915
1.50k
  ctx = isl_vec_get_ctx(v);
916
1.50k
  isl_seq_gcd(v->el + 1, v->size - 1, &ctx->normalize_gcd);
917
1.50k
  if (isl_int_is_zero(ctx->normalize_gcd) ||
918
1.50k
      
isl_int_is_one1.10k
(ctx->normalize_gcd)) {
919
1.32k
    return v;
920
1.32k
  }
921
180
922
180
  v = isl_vec_cow(v);
923
180
  if (!v)
924
0
    return NULL;
925
180
926
180
  isl_int_fdiv_r(v->el[0], v->el[0], ctx->normalize_gcd);
927
180
  if (isl_int_is_zero(v->el[0]))
928
180
    
return v66
;
929
114
930
114
  if (isl_tab_extend_cons(info->tab, 1) < 0)
931
0
    return isl_vec_free(v);
932
114
933
114
  isl_int_sub(info->bmap->ineq[ineq][0],
934
114
        info->bmap->ineq[ineq][0], v->el[0]);
935
114
  r = isl_tab_add_ineq(info->tab, info->bmap->ineq[ineq]);
936
114
  isl_int_add(info->bmap->ineq[ineq][0],
937
114
        info->bmap->ineq[ineq][0], v->el[0]);
938
114
939
114
  if (r < 0)
940
0
    return isl_vec_free(v);
941
114
942
114
  return v;
943
114
}
944
945
/* Tighten the (non-redundant) constraints on the facet represented
946
 * by info->tab.
947
 * In particular, on input, info->tab represents the result
948
 * of relaxing the "n" inequality constraints of info->bmap in "relaxed"
949
 * by one, i.e., replacing f_i >= 0 by f_i + 1 >= 0, and then
950
 * replacing the one at index "l" by the corresponding equality,
951
 * i.e., f_k + 1 = 0, with k = relaxed[l].
952
 *
953
 * Compute a variable compression from the equality constraint f_k + 1 = 0
954
 * and use it to tighten the other constraints of info->bmap
955
 * (that is, all constraints that have not been relaxed),
956
 * updating info->tab (and leaving info->bmap untouched).
957
 * The compression handles essentially two cases, one where a variable
958
 * is assigned a fixed value and can therefore be eliminated, and one
959
 * where one variable is a shifted multiple of some other variable and
960
 * can therefore be replaced by that multiple.
961
 * Gaussian elimination would also work for the first case, but for
962
 * the second case, the effectiveness would depend on the order
963
 * of the variables.
964
 * After compression, some of the constraints may have coefficients
965
 * with a common divisor.  If this divisor does not divide the constant
966
 * term, then the constraint can be tightened.
967
 * The tightening is performed on the tableau info->tab by introducing
968
 * extra (temporary) constraints.
969
 *
970
 * Only constraints that are possibly affected by the compression are
971
 * considered.  In particular, if the constraint only involves variables
972
 * that are directly mapped to a distinct set of other variables, then
973
 * no common divisor can be introduced and no tightening can occur.
974
 *
975
 * It is important to only consider the non-redundant constraints
976
 * since the facet constraint has been relaxed prior to the call
977
 * to this function, meaning that the constraints that were redundant
978
 * prior to the relaxation may no longer be redundant.
979
 * These constraints will be ignored in the fused result, so
980
 * the fusion detection should not exploit them.
981
 */
982
static isl_stat tighten_on_relaxed_facet(struct isl_coalesce_info *info,
983
  int n, int *relaxed, int l)
984
1.90k
{
985
1.90k
  unsigned total;
986
1.90k
  isl_ctx *ctx;
987
1.90k
  isl_vec *v = NULL;
988
1.90k
  isl_mat *T;
989
1.90k
  int i;
990
1.90k
  int k;
991
1.90k
  int *affected;
992
1.90k
993
1.90k
  k = relaxed[l];
994
1.90k
  ctx = isl_basic_map_get_ctx(info->bmap);
995
1.90k
  total = isl_basic_map_total_dim(info->bmap);
996
1.90k
  isl_int_add_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1);
997
1.90k
  T = isl_mat_sub_alloc6(ctx, info->bmap->ineq, k, 1, 0, 1 + total);
998
1.90k
  T = isl_mat_variable_compression(T, NULL);
999
1.90k
  isl_int_sub_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1);
1000
1.90k
  if (!T)
1001
0
    return isl_stat_error;
1002
1.90k
  if (T->n_col == 0) {
1003
0
    isl_mat_free(T);
1004
0
    return isl_stat_ok;
1005
0
  }
1006
1.90k
1007
1.90k
  affected = isl_alloc_array(ctx, int, total);
1008
1.90k
  if (!affected)
1009
0
    goto error;
1010
1.90k
1011
12.3k
  
for (i = 0; 1.90k
i < total;
++i10.4k
)
1012
10.4k
    affected[i] = not_unique_unit_row(T, 1 + i);
1013
1.90k
1014
10.2k
  for (i = 0; i < info->bmap->n_ineq; 
++i8.29k
) {
1015
8.29k
    isl_bool handle;
1016
8.29k
    if (any(relaxed, n, i))
1017
1.93k
      continue;
1018
6.35k
    if (info->ineq[i] == STATUS_REDUNDANT)
1019
6.35k
      
continue1.26k
;
1020
5.09k
    handle = is_affected(info->bmap, i, affected, total);
1021
5.09k
    if (handle < 0)
1022
0
      goto error;
1023
5.09k
    if (!handle)
1024
3.59k
      continue;
1025
1.50k
    v = isl_vec_alloc(ctx, 1 + total);
1026
1.50k
    if (!v)
1027
0
      goto error;
1028
1.50k
    isl_seq_cpy(v->el, info->bmap->ineq[i], 1 + total);
1029
1.50k
    v = isl_vec_mat_product(v, isl_mat_copy(T));
1030
1.50k
    v = try_tightening(info, i, v);
1031
1.50k
    isl_vec_free(v);
1032
1.50k
    if (!v)
1033
0
      goto error;
1034
1.50k
  }
1035
1.90k
1036
1.90k
  isl_mat_free(T);
1037
1.90k
  free(affected);
1038
1.90k
  return isl_stat_ok;
1039
0
error:
1040
0
  isl_mat_free(T);
1041
0
  free(affected);
1042
0
  return isl_stat_error;
1043
1.90k
}
1044
1045
/* Replace the basic maps "i" and "j" by an extension of "i"
1046
 * along the "n" inequality constraints in "relax" by one.
1047
 * The tableau info[i].tab has already been extended.
1048
 * Extend info[i].bmap accordingly by relaxing all constraints in "relax"
1049
 * by one.
1050
 * Each integer division that does not have exactly the same
1051
 * definition in "i" and "j" is marked unknown and the basic map
1052
 * is scheduled to be simplified in an attempt to recover
1053
 * the integer division definition.
1054
 * Place the extension in the position that is the smallest of i and j.
1055
 */
1056
static enum isl_change extend(int i, int j, int n, int *relax,
1057
  struct isl_coalesce_info *info)
1058
571
{
1059
571
  int l;
1060
571
  unsigned total;
1061
571
1062
571
  info[i].bmap = isl_basic_map_cow(info[i].bmap);
1063
571
  if (!info[i].bmap)
1064
0
    return isl_change_error;
1065
571
  total = isl_basic_map_total_dim(info[i].bmap);
1066
631
  for (l = 0; l < info[i].bmap->n_div; 
++l60
)
1067
60
    if (!isl_seq_eq(info[i].bmap->div[l],
1068
60
        info[j].bmap->div[l], 1 + 1 + total)) {
1069
22
      isl_int_set_si(info[i].bmap->div[l][0], 0);
1070
22
      info[i].simplify = 1;
1071
22
    }
1072
1.14k
  for (l = 0; l < n; 
++l575
)
1073
575
    isl_int_add_ui(info[i].bmap->ineq[relax[l]][0],
1074
571
        info[i].bmap->ineq[relax[l]][0], 1);
1075
571
  ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_FINAL);
1076
571
  drop(&info[j]);
1077
571
  if (j < i)
1078
260
    exchange(&info[i], &info[j]);
1079
571
  return isl_change_fuse;
1080
571
}
1081
1082
/* Basic map "i" has "n" inequality constraints (collected in "relax")
1083
 * that are such that they include basic map "j" if they are relaxed
1084
 * by one.  All the other inequalities are valid for "j".
1085
 * Check if basic map "j" forms an extension of basic map "i".
1086
 *
1087
 * In particular, relax the constraints in "relax", compute the corresponding
1088
 * facets one by one and check whether each of these is included
1089
 * in the other basic map.
1090
 * Before testing for inclusion, the constraints on each facet
1091
 * are tightened to increase the chance of an inclusion being detected.
1092
 * (Adding the valid constraints of "j" to the tableau of "i", as is done
1093
 * in is_adj_ineq_extension, may further increase those chances, but this
1094
 * is not currently done.)
1095
 * If each facet is included, we know that relaxing the constraints extends
1096
 * the basic map with exactly the other basic map (we already know that this
1097
 * other basic map is included in the extension, because all other
1098
 * inequality constraints are valid of "j") and we can replace the
1099
 * two basic maps by this extension.
1100
 *
1101
 * If any of the relaxed constraints turn out to be redundant, then bail out.
1102
 * isl_tab_select_facet refuses to handle such constraints.  It may be
1103
 * possible to handle them anyway by making a distinction between
1104
 * redundant constraints with a corresponding facet that still intersects
1105
 * the set (allowing isl_tab_select_facet to handle them) and
1106
 * those where the facet does not intersect the set (which can be ignored
1107
 * because the empty facet is trivially included in the other disjunct).
1108
 * However, relaxed constraints that turn out to be redundant should
1109
 * be fairly rare and no such instance has been reported where
1110
 * coalescing would be successful.
1111
 *        ____        _____
1112
 *       /    ||     /     |
1113
 *      /     ||      /      |
1114
 *      \     ||    =>  \      |
1115
 *       \    ||     \     |
1116
 *        \___||      \____|
1117
 *
1118
 *
1119
 *   \      |\
1120
 *  |\\     | \
1121
 *  | \\      |  \
1122
 *  |  |    =>  |  /
1123
 *  | /     | /
1124
 *  |/      |/
1125
 */
1126
static enum isl_change is_relaxed_extension(int i, int j, int n, int *relax,
1127
  struct isl_coalesce_info *info)
1128
1.89k
{
1129
1.89k
  int l;
1130
1.89k
  isl_bool super;
1131
1.89k
  struct isl_tab_undo *snap, *snap2;
1132
1.89k
  unsigned n_eq = info[i].bmap->n_eq;
1133
1.89k
1134
3.80k
  for (l = 0; l < n; 
++l1.91k
)
1135
1.91k
    if (isl_tab_is_equality(info[i].tab, n_eq + relax[l]))
1136
0
      return isl_change_none;
1137
1.89k
1138
1.89k
  snap = isl_tab_snap(info[i].tab);
1139
3.80k
  for (l = 0; l < n; 
++l1.91k
)
1140
1.91k
    if (isl_tab_relax(info[i].tab, n_eq + relax[l]) < 0)
1141
0
      return isl_change_error;
1142
3.80k
  
for (l = 0; 1.89k
l < n;
++l1.91k
) {
1143
1.91k
    if (!isl_tab_is_redundant(info[i].tab, n_eq + relax[l]))
1144
1.91k
      continue;
1145
0
    if (isl_tab_rollback(info[i].tab, snap) < 0)
1146
0
      return isl_change_error;
1147
0
    return isl_change_none;
1148
0
  }
1149
1.89k
  snap2 = isl_tab_snap(info[i].tab);
1150
2.47k
  for (l = 0; l < n; 
++l583
) {
1151
1.90k
    if (isl_tab_rollback(info[i].tab, snap2) < 0)
1152
0
      return isl_change_error;
1153
1.90k
    if (isl_tab_select_facet(info[i].tab, n_eq + relax[l]) < 0)
1154
0
      return isl_change_error;
1155
1.90k
    if (tighten_on_relaxed_facet(&info[i], n, relax, l) < 0)
1156
0
      return isl_change_error;
1157
1.90k
    super = contains(&info[j], info[i].tab);
1158
1.90k
    if (super < 0)
1159
0
      return isl_change_error;
1160
1.90k
    if (super)
1161
583
      continue;
1162
1.32k
    if (isl_tab_rollback(info[i].tab, snap) < 0)
1163
0
      return isl_change_error;
1164
1.32k
    return isl_change_none;
1165
1.32k
  }
1166
1.89k
1167
1.89k
  
if (571
isl_tab_rollback(info[i].tab, snap2) < 0571
)
1168
0
    return isl_change_error;
1169
571
  return extend(i, j, n, relax, info);
1170
571
}
1171
1172
/* Data structure that keeps track of the wrapping constraints
1173
 * and of information to bound the coefficients of those constraints.
1174
 *
1175
 * bound is set if we want to apply a bound on the coefficients
1176
 * mat contains the wrapping constraints
1177
 * max is the bound on the coefficients (if bound is set)
1178
 */
1179
struct isl_wraps {
1180
  int bound;
1181
  isl_mat *mat;
1182
  isl_int max;
1183
};
1184
1185
/* Update wraps->max to be greater than or equal to the coefficients
1186
 * in the equalities and inequalities of info->bmap that can be removed
1187
 * if we end up applying wrapping.
1188
 */
1189
static isl_stat wraps_update_max(struct isl_wraps *wraps,
1190
  struct isl_coalesce_info *info)
1191
8.01k
{
1192
8.01k
  int k;
1193
8.01k
  isl_int max_k;
1194
8.01k
  unsigned total = isl_basic_map_total_dim(info->bmap);
1195
8.01k
1196
8.01k
  isl_int_init(max_k);
1197
8.01k
1198
29.1k
  for (k = 0; k < info->bmap->n_eq; 
++k21.1k
) {
1199
21.1k
    if (info->eq[2 * k] == STATUS_VALID &&
1200
21.1k
        
info->eq[2 * k + 1] == 14.8k
STATUS_VALID14.8k
)
1201
21.1k
      
continue10.3k
;
1202
10.8k
    isl_seq_abs_max(info->bmap->eq[k] + 1, total, &max_k);
1203
10.8k
    if (isl_int_abs_gt(max_k, wraps->max))
1204
10.8k
      
isl_int_set2.18k
(wraps->max, max_k);
1205
10.8k
  }
1206
8.01k
1207
36.2k
  for (k = 0; k < info->bmap->n_ineq; 
++k28.1k
) {
1208
28.1k
    if (info->ineq[k] == STATUS_VALID ||
1209
28.1k
        
info->ineq[k] == 10.2k
STATUS_REDUNDANT10.2k
)
1210
28.1k
      
continue20.8k
;
1211
7.36k
    isl_seq_abs_max(info->bmap->ineq[k] + 1, total, &max_k);
1212
7.36k
    if (isl_int_abs_gt(max_k, wraps->max))
1213
7.36k
      
isl_int_set2.23k
(wraps->max, max_k);
1214
7.36k
  }
1215
8.01k
1216
8.01k
  isl_int_clear(max_k);
1217
8.01k
1218
8.01k
  return isl_stat_ok;
1219
8.01k
}
1220
1221
/* Initialize the isl_wraps data structure.
1222
 * If we want to bound the coefficients of the wrapping constraints,
1223
 * we set wraps->max to the largest coefficient
1224
 * in the equalities and inequalities that can be removed if we end up
1225
 * applying wrapping.
1226
 */
1227
static isl_stat wraps_init(struct isl_wraps *wraps, __isl_take isl_mat *mat,
1228
  struct isl_coalesce_info *info, int i, int j)
1229
4.01k
{
1230
4.01k
  isl_ctx *ctx;
1231
4.01k
1232
4.01k
  wraps->bound = 0;
1233
4.01k
  wraps->mat = mat;
1234
4.01k
  if (!mat)
1235
0
    return isl_stat_error;
1236
4.01k
  ctx = isl_mat_get_ctx(mat);
1237
4.01k
  wraps->bound = isl_options_get_coalesce_bounded_wrapping(ctx);
1238
4.01k
  if (!wraps->bound)
1239
5
    return isl_stat_ok;
1240
4.00k
  isl_int_init(wraps->max);
1241
4.00k
  isl_int_set_si(wraps->max, 0);
1242
4.00k
  if (wraps_update_max(wraps, &info[i]) < 0)
1243
0
    return isl_stat_error;
1244
4.00k
  if (wraps_update_max(wraps, &info[j]) < 0)
1245
0
    return isl_stat_error;
1246
4.00k
1247
4.00k
  return isl_stat_ok;
1248
4.00k
}
1249
1250
/* Free the contents of the isl_wraps data structure.
1251
 */
1252
static void wraps_free(struct isl_wraps *wraps)
1253
4.01k
{
1254
4.01k
  isl_mat_free(wraps->mat);
1255
4.01k
  if (wraps->bound)
1256
4.01k
    
isl_int_clear4.00k
(wraps->max);
1257
4.01k
}
1258
1259
/* Is the wrapping constraint in row "row" allowed?
1260
 *
1261
 * If wraps->bound is set, we check that none of the coefficients
1262
 * is greater than wraps->max.
1263
 */
1264
static int allow_wrap(struct isl_wraps *wraps, int row)
1265
2.52k
{
1266
2.52k
  int i;
1267
2.52k
1268
2.52k
  if (!wraps->bound)
1269
13
    return 1;
1270
2.50k
1271
14.8k
  
for (i = 1; 2.50k
i < wraps->mat->n_col;
++i12.3k
)
1272
12.9k
    if (isl_int_abs_gt(wraps->mat->row[row][i], wraps->max))
1273
12.9k
      
return 0565
;
1274
2.50k
1275
2.50k
  
return 11.94k
;
1276
2.50k
}
1277
1278
/* Wrap "ineq" (or its opposite if "negate" is set) around "bound"
1279
 * to include "set" and add the result in position "w" of "wraps".
1280
 * "len" is the total number of coefficients in "bound" and "ineq".
1281
 * Return 1 on success, 0 on failure and -1 on error.
1282
 * Wrapping can fail if the result of wrapping is equal to "bound"
1283
 * or if we want to bound the sizes of the coefficients and
1284
 * the wrapped constraint does not satisfy this bound.
1285
 */
1286
static int add_wrap(struct isl_wraps *wraps, int w, isl_int *bound,
1287
  isl_int *ineq, unsigned len, __isl_keep isl_set *set, int negate)
1288
5.33k
{
1289
5.33k
  isl_seq_cpy(wraps->mat->row[w], bound, len);
1290
5.33k
  if (negate) {
1291
1.01k
    isl_seq_neg(wraps->mat->row[w + 1], ineq, len);
1292
1.01k
    ineq = wraps->mat->row[w + 1];
1293
1.01k
  }
1294
5.33k
  if (!isl_set_wrap_facet(set, wraps->mat->row[w], ineq))
1295
0
    return -1;
1296
5.33k
  if (isl_seq_eq(wraps->mat->row[w], bound, len))
1297
2.81k
    return 0;
1298
2.52k
  if (!allow_wrap(wraps, w))
1299
565
    return 0;
1300
1.95k
  return 1;
1301
1.95k
}
1302
1303
/* For each constraint in info->bmap that is not redundant (as determined
1304
 * by info->tab) and that is not a valid constraint for the other basic map,
1305
 * wrap the constraint around "bound" such that it includes the whole
1306
 * set "set" and append the resulting constraint to "wraps".
1307
 * Note that the constraints that are valid for the other basic map
1308
 * will be added to the combined basic map by default, so there is
1309
 * no need to wrap them.
1310
 * The caller wrap_in_facets even relies on this function not wrapping
1311
 * any constraints that are already valid.
1312
 * "wraps" is assumed to have been pre-allocated to the appropriate size.
1313
 * wraps->n_row is the number of actual wrapped constraints that have
1314
 * been added.
1315
 * If any of the wrapping problems results in a constraint that is
1316
 * identical to "bound", then this means that "set" is unbounded in such
1317
 * way that no wrapping is possible.  If this happens then wraps->n_row
1318
 * is reset to zero.
1319
 * Similarly, if we want to bound the coefficients of the wrapping
1320
 * constraints and a newly added wrapping constraint does not
1321
 * satisfy the bound, then wraps->n_row is also reset to zero.
1322
 */
1323
static isl_stat add_wraps(struct isl_wraps *wraps,
1324
  struct isl_coalesce_info *info, isl_int *bound, __isl_keep isl_set *set)
1325
5.04k
{
1326
5.04k
  int l, m;
1327
5.04k
  int w;
1328
5.04k
  int added;
1329
5.04k
  isl_basic_map *bmap = info->bmap;
1330
5.04k
  unsigned len = 1 + isl_basic_map_total_dim(bmap);
1331
5.04k
1332
5.04k
  w = wraps->mat->n_row;
1333
5.04k
1334
15.4k
  for (l = 0; l < bmap->n_ineq; 
++l10.4k
) {
1335
13.3k
    if (info->ineq[l] == STATUS_VALID ||
1336
13.3k
        
info->ineq[l] == 4.73k
STATUS_REDUNDANT4.73k
)
1337
13.3k
      
continue9.54k
;
1338
3.76k
    if (isl_seq_is_neg(bound, bmap->ineq[l], len))
1339
255
      continue;
1340
3.50k
    if (isl_seq_eq(bound, bmap->ineq[l], len))
1341
0
      continue;
1342
3.50k
    if (isl_tab_is_redundant(info->tab, bmap->n_eq + l))
1343
26
      continue;
1344
3.48k
1345
3.48k
    added = add_wrap(wraps, w, bound, bmap->ineq[l], len, set, 0);
1346
3.48k
    if (added < 0)
1347
0
      return isl_stat_error;
1348
3.48k
    if (!added)
1349
2.86k
      goto unbounded;
1350
619
    ++w;
1351
619
  }
1352
6.99k
  
for (l = 0; 2.18k
l < bmap->n_eq;
++l4.81k
) {
1353
5.33k
    if (isl_seq_is_neg(bound, bmap->eq[l], len))
1354
619
      continue;
1355
4.71k
    if (isl_seq_eq(bound, bmap->eq[l], len))
1356
918
      continue;
1357
3.79k
1358
10.5k
    
for (m = 0; 3.79k
m < 2;
++m6.78k
) {
1359
7.30k
      if (info->eq[2 * l + m] == STATUS_VALID)
1360
7.30k
        
continue5.45k
;
1361
1.85k
      added = add_wrap(wraps, w, bound, bmap->eq[l], len,
1362
1.85k
          set, !m);
1363
1.85k
      if (added < 0)
1364
0
        return isl_stat_error;
1365
1.85k
      if (!added)
1366
518
        goto unbounded;
1367
1.33k
      ++w;
1368
1.33k
    }
1369
3.79k
  }
1370
2.18k
1371
2.18k
  wraps->mat->n_row = w;
1372
1.66k
  return isl_stat_ok;
1373
3.37k
unbounded:
1374
3.37k
  wraps->mat->n_row = 0;
1375
3.37k
  return isl_stat_ok;
1376
2.18k
}
1377
1378
/* Check if the constraints in "wraps" from "first" until the last
1379
 * are all valid for the basic set represented by "tab".
1380
 * If not, wraps->n_row is set to zero.
1381
 */
1382
static int check_wraps(__isl_keep isl_mat *wraps, int first,
1383
  struct isl_tab *tab)
1384
283
{
1385
283
  int i;
1386
283
1387
293
  for (i = first; i < wraps->n_row; 
++i10
) {
1388
16
    enum isl_ineq_type type;
1389
16
    type = isl_tab_ineq_type(tab, wraps->row[i]);
1390
16
    if (type == isl_ineq_error)
1391
0
      return -1;
1392
16
    if (type == isl_ineq_redundant)
1393
10
      continue;
1394
6
    wraps->n_row = 0;
1395
6
    return 0;
1396
6
  }
1397
283
1398
283
  
return 0277
;
1399
283
}
1400
1401
/* Return a set that corresponds to the non-redundant constraints
1402
 * (as recorded in tab) of bmap.
1403
 *
1404
 * It's important to remove the redundant constraints as some
1405
 * of the other constraints may have been modified after the
1406
 * constraints were marked redundant.
1407
 * In particular, a constraint may have been relaxed.
1408
 * Redundant constraints are ignored when a constraint is relaxed
1409
 * and should therefore continue to be ignored ever after.
1410
 * Otherwise, the relaxation might be thwarted by some of
1411
 * these constraints.
1412
 *
1413
 * Update the underlying set to ensure that the dimension doesn't change.
1414
 * Otherwise the integer divisions could get dropped if the tab
1415
 * turns out to be empty.
1416
 */
1417
static __isl_give isl_set *set_from_updated_bmap(__isl_keep isl_basic_map *bmap,
1418
  struct isl_tab *tab)
1419
7.85k
{
1420
7.85k
  isl_basic_set *bset;
1421
7.85k
1422
7.85k
  bmap = isl_basic_map_copy(bmap);
1423
7.85k
  bset = isl_basic_map_underlying_set(bmap);
1424
7.85k
  bset = isl_basic_set_cow(bset);
1425
7.85k
  bset = isl_basic_set_update_from_tab(bset, tab);
1426
7.85k
  return isl_set_from_basic_set(bset);
1427
7.85k
}
1428
1429
/* Wrap the constraints of info->bmap that bound the facet defined
1430
 * by inequality "k" around (the opposite of) this inequality to
1431
 * include "set".  "bound" may be used to store the negated inequality.
1432
 * Since the wrapped constraints are not guaranteed to contain the whole
1433
 * of info->bmap, we check them in check_wraps.
1434
 * If any of the wrapped constraints turn out to be invalid, then
1435
 * check_wraps will reset wrap->n_row to zero.
1436
 */
1437
static isl_stat add_wraps_around_facet(struct isl_wraps *wraps,
1438
  struct isl_coalesce_info *info, int k, isl_int *bound,
1439
  __isl_keep isl_set *set)
1440
283
{
1441
283
  struct isl_tab_undo *snap;
1442
283
  int n;
1443
283
  unsigned total = isl_basic_map_total_dim(info->bmap);
1444
283
1445
283
  snap = isl_tab_snap(info->tab);
1446
283
1447
283
  if (isl_tab_select_facet(info->tab, info->bmap->n_eq + k) < 0)
1448
0
    return isl_stat_error;
1449
283
  if (isl_tab_detect_redundant(info->tab) < 0)
1450
0
    return isl_stat_error;
1451
283
1452
283
  isl_seq_neg(bound, info->bmap->ineq[k], 1 + total);
1453
283
1454
283
  n = wraps->mat->n_row;
1455
283
  if (add_wraps(wraps, info, bound, set) < 0)
1456
0
    return isl_stat_error;
1457
283
1458
283
  if (isl_tab_rollback(info->tab, snap) < 0)
1459
0
    return isl_stat_error;
1460
283
  if (check_wraps(wraps->mat, n, info->tab) < 0)
1461
0
    return isl_stat_error;
1462
283
1463
283
  return isl_stat_ok;
1464
283
}
1465
1466
/* Given a basic set i with a constraint k that is adjacent to
1467
 * basic set j, check if we can wrap
1468
 * both the facet corresponding to k (if "wrap_facet" is set) and basic map j
1469
 * (always) around their ridges to include the other set.
1470
 * If so, replace the pair of basic sets by their union.
1471
 *
1472
 * All constraints of i (except k) are assumed to be valid or
1473
 * cut constraints for j.
1474
 * Wrapping the cut constraints to include basic map j may result
1475
 * in constraints that are no longer valid of basic map i
1476
 * we have to check that the resulting wrapping constraints are valid for i.
1477
 * If "wrap_facet" is not set, then all constraints of i (except k)
1478
 * are assumed to be valid for j.
1479
 *        ____        _____
1480
 *       /    |      /     \
1481
 *      /     ||      /      |
1482
 *      \     ||    =>  \      |
1483
 *       \    ||     \     |
1484
 *        \___||      \____|
1485
 *
1486
 */
1487
static enum isl_change can_wrap_in_facet(int i, int j, int k,
1488
  struct isl_coalesce_info *info, int wrap_facet)
1489
1.76k
{
1490
1.76k
  enum isl_change change = isl_change_none;
1491
1.76k
  struct isl_wraps wraps;
1492
1.76k
  isl_ctx *ctx;
1493
1.76k
  isl_mat *mat;
1494
1.76k
  struct isl_set *set_i = NULL;
1495
1.76k
  struct isl_set *set_j = NULL;
1496
1.76k
  struct isl_vec *bound = NULL;
1497
1.76k
  unsigned total = isl_basic_map_total_dim(info[i].bmap);
1498
1.76k
1499
1.76k
  set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
1500
1.76k
  set_j = set_from_updated_bmap(info[j].bmap, info[j].tab);
1501
1.76k
  ctx = isl_basic_map_get_ctx(info[i].bmap);
1502
1.76k
  mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
1503
1.76k
            info[i].bmap->n_ineq + info[j].bmap->n_ineq,
1504
1.76k
            1 + total);
1505
1.76k
  if (wraps_init(&wraps, mat, info, i, j) < 0)
1506
0
    goto error;
1507
1.76k
  bound = isl_vec_alloc(ctx, 1 + total);
1508
1.76k
  if (!set_i || !set_j || !bound)
1509
0
    goto error;
1510
1.76k
1511
1.76k
  isl_seq_cpy(bound->el, info[i].bmap->ineq[k], 1 + total);
1512
1.76k
  isl_int_add_ui(bound->el[0], bound->el[0], 1);
1513
1.76k
  isl_seq_normalize(ctx, bound->el, 1 + total);
1514
1.76k
1515
1.76k
  isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
1516
1.76k
  wraps.mat->n_row = 1;
1517
1.76k
1518
1.76k
  if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0)
1519
0
    goto error;
1520
1.76k
  if (!wraps.mat->n_row)
1521
1.39k
    goto unbounded;
1522
370
1523
370
  if (wrap_facet) {
1524
283
    if (add_wraps_around_facet(&wraps, &info[i], k,
1525
283
              bound->el, set_j) < 0)
1526
0
      goto error;
1527
283
    if (!wraps.mat->n_row)
1528
273
      goto unbounded;
1529
97
  }
1530
97
1531
97
  change = fuse(i, j, info, wraps.mat, 0, 0);
1532
97
1533
1.76k
unbounded:
1534
1.76k
  wraps_free(&wraps);
1535
1.76k
1536
1.76k
  isl_set_free(set_i);
1537
1.76k
  isl_set_free(set_j);
1538
1.76k
1539
1.76k
  isl_vec_free(bound);
1540
1.76k
1541
1.76k
  return change;
1542
0
error:
1543
0
  wraps_free(&wraps);
1544
0
  isl_vec_free(bound);
1545
0
  isl_set_free(set_i);
1546
0
  isl_set_free(set_j);
1547
0
  return isl_change_error;
1548
97
}
1549
1550
/* Given a cut constraint t(x) >= 0 of basic map i, stored in row "w"
1551
 * of wrap.mat, replace it by its relaxed version t(x) + 1 >= 0, and
1552
 * add wrapping constraints to wrap.mat for all constraints
1553
 * of basic map j that bound the part of basic map j that sticks out
1554
 * of the cut constraint.
1555
 * "set_i" is the underlying set of basic map i.
1556
 * If any wrapping fails, then wraps->mat.n_row is reset to zero.
1557
 *
1558
 * In particular, we first intersect basic map j with t(x) + 1 = 0.
1559
 * If the result is empty, then t(x) >= 0 was actually a valid constraint
1560
 * (with respect to the integer points), so we add t(x) >= 0 instead.
1561
 * Otherwise, we wrap the constraints of basic map j that are not
1562
 * redundant in this intersection and that are not already valid
1563
 * for basic map i over basic map i.
1564
 * Note that it is sufficient to wrap the constraints to include
1565
 * basic map i, because we will only wrap the constraints that do
1566
 * not include basic map i already.  The wrapped constraint will
1567
 * therefore be more relaxed compared to the original constraint.
1568
 * Since the original constraint is valid for basic map j, so is
1569
 * the wrapped constraint.
1570
 */
1571
static isl_stat wrap_in_facet(struct isl_wraps *wraps, int w,
1572
  struct isl_coalesce_info *info_j, __isl_keep isl_set *set_i,
1573
  struct isl_tab_undo *snap)
1574
170
{
1575
170
  isl_int_add_ui(wraps->mat->row[w][0], wraps->mat->row[w][0], 1);
1576
170
  if (isl_tab_add_eq(info_j->tab, wraps->mat->row[w]) < 0)
1577
0
    return isl_stat_error;
1578
170
  if (isl_tab_detect_redundant(info_j->tab) < 0)
1579
0
    return isl_stat_error;
1580
170
1581
170
  if (info_j->tab->empty)
1582
170
    
isl_int_sub_ui0
(wraps->mat->row[w][0], wraps->mat->row[w][0], 1);
1583
170
  else if (add_wraps(wraps, info_j, wraps->mat->row[w], set_i) < 0)
1584
0
    return isl_stat_error;
1585
170
1586
170
  if (isl_tab_rollback(info_j->tab, snap) < 0)
1587
0
    return isl_stat_error;
1588
170
1589
170
  return isl_stat_ok;
1590
170
}
1591
1592
/* Given a pair of basic maps i and j such that j sticks out
1593
 * of i at n cut constraints, each time by at most one,
1594
 * try to compute wrapping constraints and replace the two
1595
 * basic maps by a single basic map.
1596
 * The other constraints of i are assumed to be valid for j.
1597
 * "set_i" is the underlying set of basic map i.
1598
 * "wraps" has been initialized to be of the right size.
1599
 *
1600
 * For each cut constraint t(x) >= 0 of i, we add the relaxed version
1601
 * t(x) + 1 >= 0, along with wrapping constraints for all constraints
1602
 * of basic map j that bound the part of basic map j that sticks out
1603
 * of the cut constraint.
1604
 *
1605
 * If any wrapping fails, i.e., if we cannot wrap to touch
1606
 * the union, then we give up.
1607
 * Otherwise, the pair of basic maps is replaced by their union.
1608
 */
1609
static enum isl_change try_wrap_in_facets(int i, int j,
1610
  struct isl_coalesce_info *info, struct isl_wraps *wraps,
1611
  __isl_keep isl_set *set_i)
1612
164
{
1613
164
  int k, l, w;
1614
164
  unsigned total;
1615
164
  struct isl_tab_undo *snap;
1616
164
1617
164
  total = isl_basic_map_total_dim(info[i].bmap);
1618
164
1619
164
  snap = isl_tab_snap(info[j].tab);
1620
164
1621
164
  wraps->mat->n_row = 0;
1622
164
1623
205
  for (k = 0; k < info[i].bmap->n_eq; 
++k41
) {
1624
155
    for (l = 0; l < 2; 
++l89
) {
1625
114
      if (info[i].eq[2 * k + l] != STATUS_CUT)
1626
114
        
continue79
;
1627
35
      w = wraps->mat->n_row++;
1628
35
      if (l == 0)
1629
22
        isl_seq_neg(wraps->mat->row[w],
1630
22
              info[i].bmap->eq[k], 1 + total);
1631
13
      else
1632
13
        isl_seq_cpy(wraps->mat->row[w],
1633
13
              info[i].bmap->eq[k], 1 + total);
1634
35
      if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0)
1635
0
        return isl_change_error;
1636
35
1637
35
      if (!wraps->mat->n_row)
1638
25
        return isl_change_none;
1639
35
    }
1640
66
  }
1641
164
1642
913
  
for (k = 0; 139
k < info[i].bmap->n_ineq;
++k774
) {
1643
881
    if (info[i].ineq[k] != STATUS_CUT)
1644
881
      
continue746
;
1645
135
    w = wraps->mat->n_row++;
1646
135
    isl_seq_cpy(wraps->mat->row[w],
1647
135
          info[i].bmap->ineq[k], 1 + total);
1648
135
    if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0)
1649
0
      return isl_change_error;
1650
135
1651
135
    if (!wraps->mat->n_row)
1652
107
      return isl_change_none;
1653
135
  }
1654
139
1655
139
  
return fuse(i, j, info, wraps->mat, 0, 1)32
;
1656
139
}
1657
1658
/* Given a pair of basic maps i and j such that j sticks out
1659
 * of i at n cut constraints, each time by at most one,
1660
 * try to compute wrapping constraints and replace the two
1661
 * basic maps by a single basic map.
1662
 * The other constraints of i are assumed to be valid for j.
1663
 *
1664
 * The core computation is performed by try_wrap_in_facets.
1665
 * This function simply extracts an underlying set representation
1666
 * of basic map i and initializes the data structure for keeping
1667
 * track of wrapping constraints.
1668
 */
1669
static enum isl_change wrap_in_facets(int i, int j, int n,
1670
  struct isl_coalesce_info *info)
1671
164
{
1672
164
  enum isl_change change = isl_change_none;
1673
164
  struct isl_wraps wraps;
1674
164
  isl_ctx *ctx;
1675
164
  isl_mat *mat;
1676
164
  isl_set *set_i = NULL;
1677
164
  unsigned total = isl_basic_map_total_dim(info[i].bmap);
1678
164
  int max_wrap;
1679
164
1680
164
  if (isl_tab_extend_cons(info[j].tab, 1) < 0)
1681
0
    return isl_change_error;
1682
164
1683
164
  max_wrap = 1 + 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq;
1684
164
  max_wrap *= n;
1685
164
1686
164
  set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
1687
164
  ctx = isl_basic_map_get_ctx(info[i].bmap);
1688
164
  mat = isl_mat_alloc(ctx, max_wrap, 1 + total);
1689
164
  if (wraps_init(&wraps, mat, info, i, j) < 0)
1690
0
    goto error;
1691
164
  if (!set_i)
1692
0
    goto error;
1693
164
1694
164
  change = try_wrap_in_facets(i, j, info, &wraps, set_i);
1695
164
1696
164
  wraps_free(&wraps);
1697
164
  isl_set_free(set_i);
1698
164
1699
164
  return change;
1700
0
error:
1701
0
  wraps_free(&wraps);
1702
0
  isl_set_free(set_i);
1703
0
  return isl_change_error;
1704
164
}
1705
1706
/* Return the effect of inequality "ineq" on the tableau "tab",
1707
 * after relaxing the constant term of "ineq" by one.
1708
 */
1709
static enum isl_ineq_type type_of_relaxed(struct isl_tab *tab, isl_int *ineq)
1710
21.9k
{
1711
21.9k
  enum isl_ineq_type type;
1712
21.9k
1713
21.9k
  isl_int_add_ui(ineq[0], ineq[0], 1);
1714
21.9k
  type = isl_tab_ineq_type(tab, ineq);
1715
21.9k
  isl_int_sub_ui(ineq[0], ineq[0], 1);
1716
21.9k
1717
21.9k
  return type;
1718
21.9k
}
1719
1720
/* Given two basic sets i and j,
1721
 * check if relaxing all the cut constraints of i by one turns
1722
 * them into valid constraint for j and check if we can wrap in
1723
 * the bits that are sticking out.
1724
 * If so, replace the pair by their union.
1725
 *
1726
 * We first check if all relaxed cut inequalities of i are valid for j
1727
 * and then try to wrap in the intersections of the relaxed cut inequalities
1728
 * with j.
1729
 *
1730
 * During this wrapping, we consider the points of j that lie at a distance
1731
 * of exactly 1 from i.  In particular, we ignore the points that lie in
1732
 * between this lower-dimensional space and the basic map i.
1733
 * We can therefore only apply this to integer maps.
1734
 *        ____        _____
1735
 *       / ___|_     /     \
1736
 *      / |    |      /      |
1737
 *      \ |    |    =>  \      |
1738
 *       \|____|     \     |
1739
 *        \___|       \____/
1740
 *
1741
 *   _____       ______
1742
 *  | ____|_    |      \
1743
 *  | |     |   |       |
1744
 *  | | | =>  |       |
1745
 *  |_|     |   |       |
1746
 *    |_____|    \______|
1747
 *
1748
 *   _______
1749
 *  |       |
1750
 *  |  |\   |
1751
 *  |  | \  |
1752
 *  |  |  \ |
1753
 *  |  |   \|
1754
 *  |  |    \
1755
 *  |  |_____\
1756
 *  |       |
1757
 *  |_______|
1758
 *
1759
 * Wrapping can fail if the result of wrapping one of the facets
1760
 * around its edges does not produce any new facet constraint.
1761
 * In particular, this happens when we try to wrap in unbounded sets.
1762
 *
1763
 *   _______________________________________________________________________
1764
 *  |
1765
 *  |  ___
1766
 *  | |   |
1767
 *  |_|   |_________________________________________________________________
1768
 *    |___|
1769
 *
1770
 * The following is not an acceptable result of coalescing the above two
1771
 * sets as it includes extra integer points.
1772
 *   _______________________________________________________________________
1773
 *  |
1774
 *  |     
1775
 *  |      
1776
 *  |
1777
 *   \______________________________________________________________________
1778
 */
1779
static enum isl_change can_wrap_in_set(int i, int j,
1780
  struct isl_coalesce_info *info)
1781
26.3k
{
1782
26.3k
  int k, l;
1783
26.3k
  int n;
1784
26.3k
  unsigned total;
1785
26.3k
1786
26.3k
  if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) ||
1787
26.3k
      
ISL_F_ISSET21.5k
(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
1788
26.3k
    
return isl_change_none4.79k
;
1789
21.5k
1790
21.5k
  n = count_eq(&info[i], STATUS_CUT) + count_ineq(&info[i], STATUS_CUT);
1791
21.5k
  if (n == 0)
1792
0
    return isl_change_none;
1793
21.5k
1794
21.5k
  total = isl_basic_map_total_dim(info[i].bmap);
1795
21.8k
  for (k = 0; k < info[i].bmap->n_eq; 
++k319
) {
1796
3.51k
    for (l = 0; l < 2; 
++l816
) {
1797
3.19k
      enum isl_ineq_type type;
1798
3.19k
1799
3.19k
      if (info[i].eq[2 * k + l] != STATUS_CUT)
1800
3.19k
        
continue732
;
1801
2.46k
1802
2.46k
      if (l == 0)
1803
2.25k
        isl_seq_neg(info[i].bmap->eq[k],
1804
2.25k
              info[i].bmap->eq[k], 1 + total);
1805
2.46k
      type = type_of_relaxed(info[j].tab,
1806
2.46k
              info[i].bmap->eq[k]);
1807
2.46k
      if (l == 0)
1808
2.25k
        isl_seq_neg(info[i].bmap->eq[k],
1809
2.25k
              info[i].bmap->eq[k], 1 + total);
1810
2.46k
      if (type == isl_ineq_error)
1811
0
        return isl_change_error;
1812
2.46k
      if (type != isl_ineq_redundant)
1813
2.37k
        return isl_change_none;
1814
2.46k
    }
1815
2.69k
  }
1816
21.5k
1817
23.0k
  
for (k = 0; 19.1k
k < info[i].bmap->n_ineq;
++k3.92k
) {
1818
22.8k
    enum isl_ineq_type type;
1819
22.8k
1820
22.8k
    if (info[i].ineq[k] != STATUS_CUT)
1821
22.8k
      
continue3.74k
;
1822
19.1k
1823
19.1k
    type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[k]);
1824
19.1k
    if (type == isl_ineq_error)
1825
0
      return isl_change_error;
1826
19.1k
    if (type != isl_ineq_redundant)
1827
18.9k
      return isl_change_none;
1828
19.1k
  }
1829
19.1k
1830
19.1k
  
return wrap_in_facets(i, j, n, info)164
;
1831
19.1k
}
1832
1833
/* Check if either i or j has only cut constraints that can
1834
 * be used to wrap in (a facet of) the other basic set.
1835
 * if so, replace the pair by their union.
1836
 */
1837
static enum isl_change check_wrap(int i, int j, struct isl_coalesce_info *info)
1838
13.1k
{
1839
13.1k
  enum isl_change change = isl_change_none;
1840
13.1k
1841
13.1k
  change = can_wrap_in_set(i, j, info);
1842
13.1k
  if (change != isl_change_none)
1843
27
    return change;
1844
13.1k
1845
13.1k
  change = can_wrap_in_set(j, i, info);
1846
13.1k
  return change;
1847
13.1k
}
1848
1849
/* Check if all inequality constraints of "i" that cut "j" cease
1850
 * to be cut constraints if they are relaxed by one.
1851
 * If so, collect the cut constraints in "list".
1852
 * The caller is responsible for allocating "list".
1853
 */
1854
static isl_bool all_cut_by_one(int i, int j, struct isl_coalesce_info *info,
1855
  int *list)
1856
313
{
1857
313
  int l, n;
1858
313
1859
313
  n = 0;
1860
1.27k
  for (l = 0; l < info[i].bmap->n_ineq; 
++l959
) {
1861
1.25k
    enum isl_ineq_type type;
1862
1.25k
1863
1.25k
    if (info[i].ineq[l] != STATUS_CUT)
1864
1.25k
      
continue935
;
1865
316
    type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[l]);
1866
316
    if (type == isl_ineq_error)
1867
0
      return isl_bool_error;
1868
316
    if (type != isl_ineq_redundant)
1869
292
      return isl_bool_false;
1870
24
    list[n++] = l;
1871
24
  }
1872
313
1873
313
  
return isl_bool_true21
;
1874
313
}
1875
1876
/* Given two basic maps such that "j" has at least one equality constraint
1877
 * that is adjacent to an inequality constraint of "i" and such that "i" has
1878
 * exactly one inequality constraint that is adjacent to an equality
1879
 * constraint of "j", check whether "i" can be extended to include "j" or
1880
 * whether "j" can be wrapped into "i".
1881
 * All remaining constraints of "i" and "j" are assumed to be valid
1882
 * or cut constraints of the other basic map.
1883
 * However, none of the equality constraints of "i" are cut constraints.
1884
 *
1885
 * If "i" has any "cut" inequality constraints, then check if relaxing
1886
 * each of them by one is sufficient for them to become valid.
1887
 * If so, check if the inequality constraint adjacent to an equality
1888
 * constraint of "j" along with all these cut constraints
1889
 * can be relaxed by one to contain exactly "j".
1890
 * Otherwise, or if this fails, check if "j" can be wrapped into "i".
1891
 */
1892
static enum isl_change check_single_adj_eq(int i, int j,
1893
  struct isl_coalesce_info *info)
1894
2.18k
{
1895
2.18k
  enum isl_change change = isl_change_none;
1896
2.18k
  int k;
1897
2.18k
  int n_cut;
1898
2.18k
  int *relax;
1899
2.18k
  isl_ctx *ctx;
1900
2.18k
  isl_bool try_relax;
1901
2.18k
1902
2.18k
  n_cut = count_ineq(&info[i], STATUS_CUT);
1903
2.18k
1904
2.18k
  k = find_ineq(&info[i], STATUS_ADJ_EQ);
1905
2.18k
1906
2.18k
  if (n_cut > 0) {
1907
313
    ctx = isl_basic_map_get_ctx(info[i].bmap);
1908
313
    relax = isl_calloc_array(ctx, int, 1 + n_cut);
1909
313
    if (!relax)
1910
0
      return isl_change_error;
1911
313
    relax[0] = k;
1912
313
    try_relax = all_cut_by_one(i, j, info, relax + 1);
1913
313
    if (try_relax < 0)
1914
0
      change = isl_change_error;
1915
1.87k
  } else {
1916
1.87k
    try_relax = isl_bool_true;
1917
1.87k
    relax = &k;
1918
1.87k
  }
1919
2.18k
  if (try_relax && 
change == isl_change_none1.89k
)
1920
1.89k
    change = is_relaxed_extension(i, j, 1 + n_cut, relax, info);
1921
2.18k
  if (n_cut > 0)
1922
313
    free(relax);
1923
2.18k
  if (change != isl_change_none)
1924
571
    return change;
1925
1.61k
1926
1.61k
  change = can_wrap_in_facet(i, j, k, info, n_cut > 0);
1927
1.61k
1928
1.61k
  return change;
1929
1.61k
}
1930
1931
/* At least one of the basic maps has an equality that is adjacent
1932
 * to an inequality.  Make sure that only one of the basic maps has
1933
 * such an equality and that the other basic map has exactly one
1934
 * inequality adjacent to an equality.
1935
 * If the other basic map does not have such an inequality, then
1936
 * check if all its constraints are either valid or cut constraints
1937
 * and, if so, try wrapping in the first map into the second.
1938
 * Otherwise, try to extend one basic map with the other or
1939
 * wrap one basic map in the other.
1940
 */
1941
static enum isl_change check_adj_eq(int i, int j,
1942
  struct isl_coalesce_info *info)
1943
3.98k
{
1944
3.98k
  if (any_eq(&info[i], STATUS_ADJ_INEQ) &&
1945
3.98k
      
any_eq(&info[j], 882
STATUS_ADJ_INEQ882
))
1946
134
    /* ADJ EQ TOO MANY */
1947
134
    return isl_change_none;
1948
3.85k
1949
3.85k
  if (any_eq(&info[i], STATUS_ADJ_INEQ))
1950
748
    return check_adj_eq(j, i, info);
1951
3.10k
1952
3.10k
  /* j has an equality adjacent to an inequality in i */
1953
3.10k
1954
3.10k
  if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1) {
1955
493
    if (all_valid_or_cut(&info[i]))
1956
47
      return can_wrap_in_set(i, j, info);
1957
446
    return isl_change_none;
1958
446
  }
1959
2.61k
  if (any_eq(&info[i], STATUS_CUT))
1960
412
    return isl_change_none;
1961
2.20k
  if (any_ineq(&info[j], STATUS_ADJ_EQ) ||
1962
2.20k
      any_ineq(&info[i], STATUS_ADJ_INEQ) ||
1963
2.20k
      
any_ineq(&info[j], 2.18k
STATUS_ADJ_INEQ2.18k
))
1964
18
    /* ADJ EQ TOO MANY */
1965
18
    return isl_change_none;
1966
2.18k
1967
2.18k
  return check_single_adj_eq(i, j, info);
1968
2.18k
}
1969
1970
/* Disjunct "j" lies on a hyperplane that is adjacent to disjunct "i".
1971
 * In particular, disjunct "i" has an inequality constraint that is adjacent
1972
 * to a (combination of) equality constraint(s) of disjunct "j",
1973
 * but disjunct "j" has no explicit equality constraint adjacent
1974
 * to an inequality constraint of disjunct "i".
1975
 *
1976
 * Disjunct "i" is already known not to have any equality constraints
1977
 * that are adjacent to an equality or inequality constraint.
1978
 * Check that, other than the inequality constraint mentioned above,
1979
 * all other constraints of disjunct "i" are valid for disjunct "j".
1980
 * If so, try and wrap in disjunct "j".
1981
 */
1982
static enum isl_change check_ineq_adj_eq(int i, int j,
1983
  struct isl_coalesce_info *info)
1984
214
{
1985
214
  int k;
1986
214
1987
214
  if (any_eq(&info[i], STATUS_CUT))
1988
52
    return isl_change_none;
1989
162
  if (any_ineq(&info[i], STATUS_CUT))
1990
12
    return isl_change_none;
1991
150
  if (any_ineq(&info[i], STATUS_ADJ_INEQ))
1992
0
    return isl_change_none;
1993
150
  if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1)
1994
0
    return isl_change_none;
1995
150
1996
150
  k = find_ineq(&info[i], STATUS_ADJ_EQ);
1997
150
1998
150
  return can_wrap_in_facet(i, j, k, info, 0);
1999
150
}
2000
2001
/* The two basic maps lie on adjacent hyperplanes.  In particular,
2002
 * basic map "i" has an equality that lies parallel to basic map "j".
2003
 * Check if we can wrap the facets around the parallel hyperplanes
2004
 * to include the other set.
2005
 *
2006
 * We perform basically the same operations as can_wrap_in_facet,
2007
 * except that we don't need to select a facet of one of the sets.
2008
 *        _
2009
 *  \\      \\
2010
 *   \\   =>   \\
2011
 *    \       \|
2012
 *
2013
 * If there is more than one equality of "i" adjacent to an equality of "j",
2014
 * then the result will satisfy one or more equalities that are a linear
2015
 * combination of these equalities.  These will be encoded as pairs
2016
 * of inequalities in the wrapping constraints and need to be made
2017
 * explicit.
2018
 */
2019
static enum isl_change check_eq_adj_eq(int i, int j,
2020
  struct isl_coalesce_info *info)
2021
2.08k
{
2022
2.08k
  int k;
2023
2.08k
  enum isl_change change = isl_change_none;
2024
2.08k
  int detect_equalities = 0;
2025
2.08k
  struct isl_wraps wraps;
2026
2.08k
  isl_ctx *ctx;
2027
2.08k
  isl_mat *mat;
2028
2.08k
  struct isl_set *set_i = NULL;
2029
2.08k
  struct isl_set *set_j = NULL;
2030
2.08k
  struct isl_vec *bound = NULL;
2031
2.08k
  unsigned total = isl_basic_map_total_dim(info[i].bmap);
2032
2.08k
2033
2.08k
  if (count_eq(&info[i], STATUS_ADJ_EQ) != 1)
2034
522
    detect_equalities = 1;
2035
2.08k
2036
2.08k
  k = find_eq(&info[i], STATUS_ADJ_EQ);
2037
2.08k
2038
2.08k
  set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
2039
2.08k
  set_j = set_from_updated_bmap(info[j].bmap, info[j].tab);
2040
2.08k
  ctx = isl_basic_map_get_ctx(info[i].bmap);
2041
2.08k
  mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
2042
2.08k
            info[i].bmap->n_ineq + info[j].bmap->n_ineq,
2043
2.08k
            1 + total);
2044
2.08k
  if (wraps_init(&wraps, mat, info, i, j) < 0)
2045
0
    goto error;
2046
2.08k
  bound = isl_vec_alloc(ctx, 1 + total);
2047
2.08k
  if (!set_i || !set_j || !bound)
2048
0
    goto error;
2049
2.08k
2050
2.08k
  if (k % 2 == 0)
2051
834
    isl_seq_neg(bound->el, info[i].bmap->eq[k / 2], 1 + total);
2052
1.25k
  else
2053
1.25k
    isl_seq_cpy(bound->el, info[i].bmap->eq[k / 2], 1 + total);
2054
2.08k
  isl_int_add_ui(bound->el[0], bound->el[0], 1);
2055
2.08k
2056
2.08k
  isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
2057
2.08k
  wraps.mat->n_row = 1;
2058
2.08k
2059
2.08k
  if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0)
2060
0
    goto error;
2061
2.08k
  if (!wraps.mat->n_row)
2062
1.33k
    goto unbounded;
2063
746
2064
746
  isl_int_sub_ui(bound->el[0], bound->el[0], 1);
2065
746
  isl_seq_neg(bound->el, bound->el, 1 + total);
2066
746
2067
746
  isl_seq_cpy(wraps.mat->row[wraps.mat->n_row], bound->el, 1 + total);
2068
746
  wraps.mat->n_row++;
2069
746
2070
746
  if (add_wraps(&wraps, &info[i], bound->el, set_j) < 0)
2071
0
    goto error;
2072
746
  if (!wraps.mat->n_row)
2073
250
    goto unbounded;
2074
496
2075
496
  change = fuse(i, j, info, wraps.mat, detect_equalities, 0);
2076
496
2077
496
  if (0) {
2078
0
error:    change = isl_change_error;
2079
0
  }
2080
2.08k
unbounded:
2081
2.08k
2082
2.08k
  wraps_free(&wraps);
2083
2.08k
  isl_set_free(set_i);
2084
2.08k
  isl_set_free(set_j);
2085
2.08k
  isl_vec_free(bound);
2086
2.08k
2087
2.08k
  return change;
2088
496
}
2089
2090
/* Initialize the "eq" and "ineq" fields of "info".
2091
 */
2092
static void init_status(struct isl_coalesce_info *info)
2093
128k
{
2094
128k
  info->eq = info->ineq = NULL;
2095
128k
}
2096
2097
/* Set info->eq to the positions of the equalities of info->bmap
2098
 * with respect to the basic map represented by "tab".
2099
 * If info->eq has already been computed, then do not compute it again.
2100
 */
2101
static void set_eq_status_in(struct isl_coalesce_info *info,
2102
  struct isl_tab *tab)
2103
76.7k
{
2104
76.7k
  if (info->eq)
2105
2.54k
    return;
2106
74.1k
  info->eq = eq_status_in(info->bmap, tab);
2107
74.1k
}
2108
2109
/* Set info->ineq to the positions of the inequalities of info->bmap
2110
 * with respect to the basic map represented by "tab".
2111
 * If info->ineq has already been computed, then do not compute it again.
2112
 */
2113
static void set_ineq_status_in(struct isl_coalesce_info *info,
2114
  struct isl_tab *tab)
2115
103k
{
2116
103k
  if (info->ineq)
2117
2.57k
    return;
2118
101k
  info->ineq = ineq_status_in(info->bmap, info->tab, tab);
2119
101k
}
2120
2121
/* Free the memory allocated by the "eq" and "ineq" fields of "info".
2122
 * This function assumes that init_status has been called on "info" first,
2123
 * after which the "eq" and "ineq" fields may or may not have been
2124
 * assigned a newly allocated array.
2125
 */
2126
static void clear_status(struct isl_coalesce_info *info)
2127
128k
{
2128
128k
  free(info->eq);
2129
128k
  free(info->ineq);
2130
128k
}
2131
2132
/* Are all inequality constraints of the basic map represented by "info"
2133
 * valid for the other basic map, except for a single constraint
2134
 * that is adjacent to an inequality constraint of the other basic map?
2135
 */
2136
static int all_ineq_valid_or_single_adj_ineq(struct isl_coalesce_info *info)
2137
133
{
2138
133
  int i;
2139
133
  int k = -1;
2140
133
2141
451
  for (i = 0; i < info->bmap->n_ineq; 
++i318
) {
2142
440
    if (info->ineq[i] == STATUS_REDUNDANT)
2143
440
      
continue81
;
2144
359
    if (info->ineq[i] == STATUS_VALID)
2145
359
      
continue200
;
2146
159
    if (info->ineq[i] != STATUS_ADJ_INEQ)
2147
159
      
return 0121
;
2148
38
    if (k != -1)
2149
1
      return 0;
2150
37
    k = i;
2151
37
  }
2152
133
2153
133
  
return k != -111
;
2154
133
}
2155
2156
/* Basic map "i" has one or more equality constraints that separate it
2157
 * from basic map "j".  Check if it happens to be an extension
2158
 * of basic map "j".
2159
 * In particular, check that all constraints of "j" are valid for "i",
2160
 * except for one inequality constraint that is adjacent
2161
 * to an inequality constraints of "i".
2162
 * If so, check for "i" being an extension of "j" by calling
2163
 * is_adj_ineq_extension.
2164
 *
2165
 * Clean up the memory allocated for keeping track of the status
2166
 * of the constraints before returning.
2167
 */
2168
static enum isl_change separating_equality(int i, int j,
2169
  struct isl_coalesce_info *info)
2170
5.34k
{
2171
5.34k
  enum isl_change change = isl_change_none;
2172
5.34k
2173
5.34k
  if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2174
5.34k
      
all_ineq_valid_or_single_adj_ineq(&info[j])133
)
2175
11
    change = is_adj_ineq_extension(j, i, info);
2176
5.34k
2177
5.34k
  clear_status(&info[i]);
2178
5.34k
  clear_status(&info[j]);
2179
5.34k
  return change;
2180
5.34k
}
2181
2182
/* Check if the union of the given pair of basic maps
2183
 * can be represented by a single basic map.
2184
 * If so, replace the pair by the single basic map and return
2185
 * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
2186
 * Otherwise, return isl_change_none.
2187
 * The two basic maps are assumed to live in the same local space.
2188
 * The "eq" and "ineq" fields of info[i] and info[j] are assumed
2189
 * to have been initialized by the caller, either to NULL or
2190
 * to valid information.
2191
 *
2192
 * We first check the effect of each constraint of one basic map
2193
 * on the other basic map.
2194
 * The constraint may be
2195
 *  redundant the constraint is redundant in its own
2196
 *      basic map and should be ignore and removed
2197
 *      in the end
2198
 *  valid   all (integer) points of the other basic map
2199
 *      satisfy the constraint
2200
 *  separate  no (integer) point of the other basic map
2201
 *      satisfies the constraint
2202
 *  cut   some but not all points of the other basic map
2203
 *      satisfy the constraint
2204
 *  adj_eq    the given constraint is adjacent (on the outside)
2205
 *      to an equality of the other basic map
2206
 *  adj_ineq  the given constraint is adjacent (on the outside)
2207
 *      to an inequality of the other basic map
2208
 *
2209
 * We consider seven cases in which we can replace the pair by a single
2210
 * basic map.  We ignore all "redundant" constraints.
2211
 *
2212
 *  1. all constraints of one basic map are valid
2213
 *    => the other basic map is a subset and can be removed
2214
 *
2215
 *  2. all constraints of both basic maps are either "valid" or "cut"
2216
 *     and the facets corresponding to the "cut" constraints
2217
 *     of one of the basic maps lies entirely inside the other basic map
2218
 *    => the pair can be replaced by a basic map consisting
2219
 *       of the valid constraints in both basic maps
2220
 *
2221
 *  3. there is a single pair of adjacent inequalities
2222
 *     (all other constraints are "valid")
2223
 *    => the pair can be replaced by a basic map consisting
2224
 *       of the valid constraints in both basic maps
2225
 *
2226
 *  4. one basic map has a single adjacent inequality, while the other
2227
 *     constraints are "valid".  The other basic map has some
2228
 *     "cut" constraints, but replacing the adjacent inequality by
2229
 *     its opposite and adding the valid constraints of the other
2230
 *     basic map results in a subset of the other basic map
2231
 *    => the pair can be replaced by a basic map consisting
2232
 *       of the valid constraints in both basic maps
2233
 *
2234
 *  5. there is a single adjacent pair of an inequality and an equality,
2235
 *     the other constraints of the basic map containing the inequality are
2236
 *     "valid".  Moreover, if the inequality the basic map is relaxed
2237
 *     and then turned into an equality, then resulting facet lies
2238
 *     entirely inside the other basic map
2239
 *    => the pair can be replaced by the basic map containing
2240
 *       the inequality, with the inequality relaxed.
2241
 *
2242
 *  6. there is a single inequality adjacent to an equality,
2243
 *     the other constraints of the basic map containing the inequality are
2244
 *     "valid".  Moreover, the facets corresponding to both
2245
 *     the inequality and the equality can be wrapped around their
2246
 *     ridges to include the other basic map
2247
 *    => the pair can be replaced by a basic map consisting
2248
 *       of the valid constraints in both basic maps together
2249
 *       with all wrapping constraints
2250
 *
2251
 *  7. one of the basic maps extends beyond the other by at most one.
2252
 *     Moreover, the facets corresponding to the cut constraints and
2253
 *     the pieces of the other basic map at offset one from these cut
2254
 *     constraints can be wrapped around their ridges to include
2255
 *     the union of the two basic maps
2256
 *    => the pair can be replaced by a basic map consisting
2257
 *       of the valid constraints in both basic maps together
2258
 *       with all wrapping constraints
2259
 *
2260
 *  8. the two basic maps live in adjacent hyperplanes.  In principle
2261
 *     such sets can always be combined through wrapping, but we impose
2262
 *     that there is only one such pair, to avoid overeager coalescing.
2263
 *
2264
 * Throughout the computation, we maintain a collection of tableaus
2265
 * corresponding to the basic maps.  When the basic maps are dropped
2266
 * or combined, the tableaus are modified accordingly.
2267
 */
2268
static enum isl_change coalesce_local_pair_reuse(int i, int j,
2269
  struct isl_coalesce_info *info)
2270
61.3k
{
2271
61.3k
  enum isl_change change = isl_change_none;
2272
61.3k
2273
61.3k
  set_ineq_status_in(&info[i], info[j].tab);
2274
61.3k
  if (info[i].bmap->n_ineq && 
!info[i].ineq54.5k
)
2275
0
    goto error;
2276
61.3k
  if (any_ineq(&info[i], STATUS_ERROR))
2277
0
    goto error;
2278
61.3k
  if (any_ineq(&info[i], STATUS_SEPARATE))
2279
19.0k
    goto done;
2280
42.3k
2281
42.3k
  set_ineq_status_in(&info[j], info[i].tab);
2282
42.3k
  if (info[j].bmap->n_ineq && 
!info[j].ineq36.2k
)
2283
0
    goto error;
2284
42.3k
  if (any_ineq(&info[j], STATUS_ERROR))
2285
0
    goto error;
2286
42.3k
  if (any_ineq(&info[j], STATUS_SEPARATE))
2287
3.96k
    goto done;
2288
38.3k
2289
38.3k
  set_eq_status_in(&info[i], info[j].tab);
2290
38.3k
  if (info[i].bmap->n_eq && 
!info[i].eq16.9k
)
2291
0
    goto error;
2292
38.3k
  if (any_eq(&info[i], STATUS_ERROR))
2293
0
    goto error;
2294
38.3k
2295
38.3k
  set_eq_status_in(&info[j], info[i].tab);
2296
38.3k
  if (info[j].bmap->n_eq && 
!info[j].eq16.8k
)
2297
0
    goto error;
2298
38.3k
  if (any_eq(&info[j], STATUS_ERROR))
2299
0
    goto error;
2300
38.3k
2301
38.3k
  if (any_eq(&info[i], STATUS_SEPARATE))
2302
4.81k
    return separating_equality(i, j, info);
2303
33.5k
  if (any_eq(&info[j], STATUS_SEPARATE))
2304
524
    return separating_equality(j, i, info);
2305
33.0k
2306
33.0k
  if (all(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_VALID) &&
2307
33.0k
      
all(info[i].ineq, info[i].bmap->n_ineq, 23.5k
STATUS_VALID23.5k
)) {
2308
2.90k
    drop(&info[j]);
2309
2.90k
    change = isl_change_drop_second;
2310
30.1k
  } else if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2311
30.1k
       
all(info[j].ineq, info[j].bmap->n_ineq, 21.9k
STATUS_VALID21.9k
)) {
2312
2.99k
    drop(&info[i]);
2313
2.99k
    change = isl_change_drop_first;
2314
27.1k
  } else if (any_eq(&info[i], STATUS_ADJ_EQ)) {
2315
1.80k
    change = check_eq_adj_eq(i, j, info);
2316
25.3k
  } else if (any_eq(&info[j], STATUS_ADJ_EQ)) {
2317
282
    change = check_eq_adj_eq(j, i, info);
2318
25.0k
  } else if (any_eq(&info[i], STATUS_ADJ_INEQ) ||
2319
25.0k
       
any_eq(&info[j], 24.1k
STATUS_ADJ_INEQ24.1k
)) {
2320
3.24k
    change = check_adj_eq(i, j, info);
2321
21.8k
  } else if (any_ineq(&info[i], STATUS_ADJ_EQ)) {
2322
99
    change = check_ineq_adj_eq(i, j, info);
2323
21.7k
  } else if (any_ineq(&info[j], STATUS_ADJ_EQ)) {
2324
115
    change = check_ineq_adj_eq(j, i, info);
2325
21.5k
  } else if (any_ineq(&info[i], STATUS_ADJ_INEQ) ||
2326
21.5k
       
any_ineq(&info[j], 13.2k
STATUS_ADJ_INEQ13.2k
)) {
2327
8.41k
    change = check_adj_ineq(i, j, info);
2328
13.1k
  } else {
2329
13.1k
    if (!any_eq(&info[i], STATUS_CUT) &&
2330
13.1k
        
!any_eq(&info[j], 9.61k
STATUS_CUT9.61k
))
2331
9.50k
      change = check_facets(i, j, info);
2332
13.1k
    if (change == isl_change_none)
2333
13.1k
      change = check_wrap(i, j, info);
2334
13.1k
  }
2335
33.0k
2336
56.0k
done:
2337
56.0k
  clear_status(&info[i]);
2338
56.0k
  clear_status(&info[j]);
2339
56.0k
  return change;
2340
0
error:
2341
0
  clear_status(&info[i]);
2342
0
  clear_status(&info[j]);
2343
0
  return isl_change_error;
2344
33.0k
}
2345
2346
/* Check if the union of the given pair of basic maps
2347
 * can be represented by a single basic map.
2348
 * If so, replace the pair by the single basic map and return
2349
 * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
2350
 * Otherwise, return isl_change_none.
2351
 * The two basic maps are assumed to live in the same local space.
2352
 */
2353
static enum isl_change coalesce_local_pair(int i, int j,
2354
  struct isl_coalesce_info *info)
2355
58.6k
{
2356
58.6k
  init_status(&info[i]);
2357
58.6k
  init_status(&info[j]);
2358
58.6k
  return coalesce_local_pair_reuse(i, j, info);
2359
58.6k
}
2360
2361
/* Shift the integer division at position "div" of the basic map
2362
 * represented by "info" by "shift".
2363
 *
2364
 * That is, if the integer division has the form
2365
 *
2366
 *  floor(f(x)/d)
2367
 *
2368
 * then replace it by
2369
 *
2370
 *  floor((f(x) + shift * d)/d) - shift
2371
 */
2372
static isl_stat shift_div(struct isl_coalesce_info *info, int div,
2373
  isl_int shift)
2374
158
{
2375
158
  unsigned total;
2376
158
2377
158
  info->bmap = isl_basic_map_shift_div(info->bmap, div, 0, shift);
2378
158
  if (!info->bmap)
2379
0
    return isl_stat_error;
2380
158
2381
158
  total = isl_basic_map_dim(info->bmap, isl_dim_all);
2382
158
  total -= isl_basic_map_dim(info->bmap, isl_dim_div);
2383
158
  if (isl_tab_shift_var(info->tab, total + div, shift) < 0)
2384
0
    return isl_stat_error;
2385
158
2386
158
  return isl_stat_ok;
2387
158
}
2388
2389
/* If the integer division at position "div" is defined by an equality,
2390
 * i.e., a stride constraint, then change the integer division expression
2391
 * to have a constant term equal to zero.
2392
 *
2393
 * Let the equality constraint be
2394
 *
2395
 *  c + f + m a = 0
2396
 *
2397
 * The integer division expression is then typically of the form
2398
 *
2399
 *  a = floor((-f - c')/m)
2400
 *
2401
 * The integer division is first shifted by t = floor(c/m),
2402
 * turning the equality constraint into
2403
 *
2404
 *  c - m floor(c/m) + f + m a' = 0
2405
 *
2406
 * i.e.,
2407
 *
2408
 *  (c mod m) + f + m a' = 0
2409
 *
2410
 * That is,
2411
 *
2412
 *  a' = (-f - (c mod m))/m = floor((-f)/m)
2413
 *
2414
 * because a' is an integer and 0 <= (c mod m) < m.
2415
 * The constant term of a' can therefore be zeroed out,
2416
 * but only if the integer division expression is of the expected form.
2417
 */
2418
static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div)
2419
560
{
2420
560
  isl_bool defined, valid;
2421
560
  isl_stat r;
2422
560
  isl_constraint *c;
2423
560
  isl_int shift, stride;
2424
560
2425
560
  defined = isl_basic_map_has_defining_equality(info->bmap, isl_dim_div,
2426
560
              div, &c);
2427
560
  if (defined < 0)
2428
0
    return isl_stat_error;
2429
560
  if (!defined)
2430
406
    return isl_stat_ok;
2431
154
  if (!c)
2432
0
    return isl_stat_error;
2433
154
  valid = isl_constraint_is_div_equality(c, div);
2434
154
  isl_int_init(shift);
2435
154
  isl_int_init(stride);
2436
154
  isl_constraint_get_constant(c, &shift);
2437
154
  isl_constraint_get_coefficient(c, isl_dim_div, div, &stride);
2438
154
  isl_int_fdiv_q(shift, shift, stride);
2439
154
  r = shift_div(info, div, shift);
2440
154
  isl_int_clear(stride);
2441
154
  isl_int_clear(shift);
2442
154
  isl_constraint_free(c);
2443
154
  if (r < 0 || valid < 0)
2444
0
    return isl_stat_error;
2445
154
  if (!valid)
2446
2
    return isl_stat_ok;
2447
152
  info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace(
2448
152
                  info->bmap, div, 0);
2449
152
  if (!info->bmap)
2450
0
    return isl_stat_error;
2451
152
  return isl_stat_ok;
2452
152
}
2453
2454
/* The basic maps represented by "info1" and "info2" are known
2455
 * to have the same number of integer divisions.
2456
 * Check if pairs of integer divisions are equal to each other
2457
 * despite the fact that they differ by a rational constant.
2458
 *
2459
 * In particular, look for any pair of integer divisions that
2460
 * only differ in their constant terms.
2461
 * If either of these integer divisions is defined
2462
 * by stride constraints, then modify it to have a zero constant term.
2463
 * If both are defined by stride constraints then in the end they will have
2464
 * the same (zero) constant term.
2465
 */
2466
static isl_stat harmonize_stride_divs(struct isl_coalesce_info *info1,
2467
  struct isl_coalesce_info *info2)
2468
4.39k
{
2469
4.39k
  int i, n;
2470
4.39k
2471
4.39k
  n = isl_basic_map_dim(info1->bmap, isl_dim_div);
2472
9.10k
  for (i = 0; i < n; 
++i4.70k
) {
2473
4.70k
    isl_bool known, harmonize;
2474
4.70k
2475
4.70k
    known = isl_basic_map_div_is_known(info1->bmap, i);
2476
4.70k
    if (known >= 0 && known)
2477
4.70k
      known = isl_basic_map_div_is_known(info2->bmap, i);
2478
4.70k
    if (known < 0)
2479
0
      return isl_stat_error;
2480
4.70k
    if (!known)
2481
5
      continue;
2482
4.70k
    harmonize = isl_basic_map_equal_div_expr_except_constant(
2483
4.70k
              info1->bmap, i, info2->bmap, i);
2484
4.70k
    if (harmonize < 0)
2485
0
      return isl_stat_error;
2486
4.70k
    if (!harmonize)
2487
4.42k
      continue;
2488
280
    if (normalize_stride_div(info1, i) < 0)
2489
0
      return isl_stat_error;
2490
280
    if (normalize_stride_div(info2, i) < 0)
2491
0
      return isl_stat_error;
2492
280
  }
2493
4.39k
2494
4.39k
  return isl_stat_ok;
2495
4.39k
}
2496
2497
/* If "shift" is an integer constant, then shift the integer division
2498
 * at position "div" of the basic map represented by "info" by "shift".
2499
 * If "shift" is not an integer constant, then do nothing.
2500
 * If "shift" is equal to zero, then no shift needs to be performed either.
2501
 *
2502
 * That is, if the integer division has the form
2503
 *
2504
 *  floor(f(x)/d)
2505
 *
2506
 * then replace it by
2507
 *
2508
 *  floor((f(x) + shift * d)/d) - shift
2509
 */
2510
static isl_stat shift_if_cst_int(struct isl_coalesce_info *info, int div,
2511
  __isl_keep isl_aff *shift)
2512
44
{
2513
44
  isl_bool cst;
2514
44
  isl_stat r;
2515
44
  isl_int d;
2516
44
  isl_val *c;
2517
44
2518
44
  cst = isl_aff_is_cst(shift);
2519
44
  if (cst < 0 || !cst)
2520
19
    return cst < 0 ? 
isl_stat_error0
: isl_stat_ok;
2521
25
2522
25
  c = isl_aff_get_constant_val(shift);
2523
25
  cst = isl_val_is_int(c);
2524
25
  if (cst >= 0 && cst)
2525
12
    cst = isl_bool_not(isl_val_is_zero(c));
2526
25
  if (cst < 0 || !cst) {
2527
21
    isl_val_free(c);
2528
21
    return cst < 0 ? 
isl_stat_error0
: isl_stat_ok;
2529
21
  }
2530
4
2531
4
  isl_int_init(d);
2532
4
  r = isl_val_get_num_isl_int(c, &d);
2533
4
  if (r >= 0)
2534
4
    r = shift_div(info, div, d);
2535
4
  isl_int_clear(d);
2536
4
2537
4
  isl_val_free(c);
2538
4
2539
4
  return r;
2540
4
}
2541
2542
/* Check if some of the divs in the basic map represented by "info1"
2543
 * are shifts of the corresponding divs in the basic map represented
2544
 * by "info2", taking into account the equality constraints "eq1" of "info1"
2545
 * and "eq2" of "info2".  If so, align them with those of "info2".
2546
 * "info1" and "info2" are assumed to have the same number
2547
 * of integer divisions.
2548
 *
2549
 * An integer division is considered to be a shift of another integer
2550
 * division if, after simplification with respect to the equality
2551
 * constraints of the other basic map, one is equal to the other
2552
 * plus a constant.
2553
 *
2554
 * In particular, for each pair of integer divisions, if both are known,
2555
 * have the same denominator and are not already equal to each other,
2556
 * simplify each with respect to the equality constraints
2557
 * of the other basic map.  If the difference is an integer constant,
2558
 * then move this difference outside.
2559
 * That is, if, after simplification, one integer division is of the form
2560
 *
2561
 *  floor((f(x) + c_1)/d)
2562
 *
2563
 * while the other is of the form
2564
 *
2565
 *  floor((f(x) + c_2)/d)
2566
 *
2567
 * and n = (c_2 - c_1)/d is an integer, then replace the first
2568
 * integer division by
2569
 *
2570
 *  floor((f_1(x) + c_1 + n * d)/d) - n,
2571
 *
2572
 * where floor((f_1(x) + c_1 + n * d)/d) = floor((f2(x) + c_2)/d)
2573
 * after simplification with respect to the equality constraints.
2574
 */
2575
static isl_stat harmonize_divs_with_hulls(struct isl_coalesce_info *info1,
2576
  struct isl_coalesce_info *info2, __isl_keep isl_basic_set *eq1,
2577
  __isl_keep isl_basic_set *eq2)
2578
270
{
2579
270
  int i;
2580
270
  int total;
2581
270
  isl_local_space *ls1, *ls2;
2582
270
2583
270
  total = isl_basic_map_total_dim(info1->bmap);
2584
270
  ls1 = isl_local_space_wrap(isl_basic_map_get_local_space(info1->bmap));
2585
270
  ls2 = isl_local_space_wrap(isl_basic_map_get_local_space(info2->bmap));
2586
581
  for (i = 0; i < info1->bmap->n_div; 
++i311
) {
2587
311
    isl_stat r;
2588
311
    isl_aff *div1, *div2;
2589
311
2590
311
    if (!isl_local_space_div_is_known(ls1, i) ||
2591
311
        
!isl_local_space_div_is_known(ls2, i)307
)
2592
5
      continue;
2593
306
    if (isl_int_ne(info1->bmap->div[i][0], info2->bmap->div[i][0]))
2594
306
      
continue42
;
2595
264
    if (isl_seq_eq(info1->bmap->div[i] + 1,
2596
264
        info2->bmap->div[i] + 1, 1 + total))
2597
220
      continue;
2598
44
    div1 = isl_local_space_get_div(ls1, i);
2599
44
    div2 = isl_local_space_get_div(ls2, i);
2600
44
    div1 = isl_aff_substitute_equalities(div1,
2601
44
                isl_basic_set_copy(eq2));
2602
44
    div2 = isl_aff_substitute_equalities(div2,
2603
44
                isl_basic_set_copy(eq1));
2604
44
    div2 = isl_aff_sub(div2, div1);
2605
44
    r = shift_if_cst_int(info1, i, div2);
2606
44
    isl_aff_free(div2);
2607
44
    if (r < 0)
2608
0
      break;
2609
44
  }
2610
270
  isl_local_space_free(ls1);
2611
270
  isl_local_space_free(ls2);
2612
270
2613
270
  if (i < info1->bmap->n_div)
2614
0
    return isl_stat_error;
2615
270
  return isl_stat_ok;
2616
270
}
2617
2618
/* Check if some of the divs in the basic map represented by "info1"
2619
 * are shifts of the corresponding divs in the basic map represented
2620
 * by "info2".  If so, align them with those of "info2".
2621
 * Only do this if "info1" and "info2" have the same number
2622
 * of integer divisions.
2623
 *
2624
 * An integer division is considered to be a shift of another integer
2625
 * division if, after simplification with respect to the equality
2626
 * constraints of the other basic map, one is equal to the other
2627
 * plus a constant.
2628
 *
2629
 * First check if pairs of integer divisions are equal to each other
2630
 * despite the fact that they differ by a rational constant.
2631
 * If so, try and arrange for them to have the same constant term.
2632
 *
2633
 * Then, extract the equality constraints and continue with
2634
 * harmonize_divs_with_hulls.
2635
 *
2636
 * If the equality constraints of both basic maps are the same,
2637
 * then there is no need to perform any shifting since
2638
 * the coefficients of the integer divisions should have been
2639
 * reduced in the same way.
2640
 */
2641
static isl_stat harmonize_divs(struct isl_coalesce_info *info1,
2642
  struct isl_coalesce_info *info2)
2643
66.2k
{
2644
66.2k
  isl_bool equal;
2645
66.2k
  isl_basic_map *bmap1, *bmap2;
2646
66.2k
  isl_basic_set *eq1, *eq2;
2647
66.2k
  isl_stat r;
2648
66.2k
2649
66.2k
  if (!info1->bmap || !info2->bmap)
2650
0
    return isl_stat_error;
2651
66.2k
2652
66.2k
  if (info1->bmap->n_div != info2->bmap->n_div)
2653
7.84k
    return isl_stat_ok;
2654
58.4k
  if (info1->bmap->n_div == 0)
2655
54.0k
    return isl_stat_ok;
2656
4.39k
2657
4.39k
  if (harmonize_stride_divs(info1, info2) < 0)
2658
0
    return isl_stat_error;
2659
4.39k
2660
4.39k
  bmap1 = isl_basic_map_copy(info1->bmap);
2661
4.39k
  bmap2 = isl_basic_map_copy(info2->bmap);
2662
4.39k
  eq1 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap1));
2663
4.39k
  eq2 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap2));
2664
4.39k
  equal = isl_basic_set_plain_is_equal(eq1, eq2);
2665
4.39k
  if (equal < 0)
2666
0
    r = isl_stat_error;
2667
4.39k
  else if (equal)
2668
4.12k
    r = isl_stat_ok;
2669
270
  else
2670
270
    r = harmonize_divs_with_hulls(info1, info2, eq1, eq2);
2671
4.39k
  isl_basic_set_free(eq1);
2672
4.39k
  isl_basic_set_free(eq2);
2673
4.39k
2674
4.39k
  return r;
2675
4.39k
}
2676
2677
/* Do the two basic maps live in the same local space, i.e.,
2678
 * do they have the same (known) divs?
2679
 * If either basic map has any unknown divs, then we can only assume
2680
 * that they do not live in the same local space.
2681
 */
2682
static isl_bool same_divs(__isl_keep isl_basic_map *bmap1,
2683
  __isl_keep isl_basic_map *bmap2)
2684
66.2k
{
2685
66.2k
  int i;
2686
66.2k
  isl_bool known;
2687
66.2k
  int total;
2688
66.2k
2689
66.2k
  if (!bmap1 || !bmap2)
2690
0
    return isl_bool_error;
2691
66.2k
  if (bmap1->n_div != bmap2->n_div)
2692
7.84k
    return isl_bool_false;
2693
58.4k
2694
58.4k
  if (bmap1->n_div == 0)
2695
54.0k
    return isl_bool_true;
2696
4.39k
2697
4.39k
  known = isl_basic_map_divs_known(bmap1);
2698
4.39k
  if (known < 0 || !known)
2699
4
    return known;
2700
4.39k
  known = isl_basic_map_divs_known(bmap2);
2701
4.39k
  if (known < 0 || !known)
2702
1
    return known;
2703
4.39k
2704
4.39k
  total = isl_basic_map_total_dim(bmap1);
2705
8.75k
  for (i = 0; i < bmap1->n_div; 
++i4.36k
)
2706
4.60k
    if (!isl_seq_eq(bmap1->div[i], bmap2->div[i], 2 + total))
2707
241
      return isl_bool_false;
2708
4.39k
2709
4.39k
  
return isl_bool_true4.15k
;
2710
4.39k
}
2711
2712
/* Assuming that "tab" contains the equality constraints and
2713
 * the initial inequality constraints of "bmap", copy the remaining
2714
 * inequality constraints of "bmap" to "Tab".
2715
 */
2716
static isl_stat copy_ineq(struct isl_tab *tab, __isl_keep isl_basic_map *bmap)
2717
2.94k
{
2718
2.94k
  int i, n_ineq;
2719
2.94k
2720
2.94k
  if (!bmap)
2721
0
    return isl_stat_error;
2722
2.94k
2723
2.94k
  n_ineq = tab->n_con - tab->n_eq;
2724
9.05k
  for (i = n_ineq; i < bmap->n_ineq; 
++i6.11k
)
2725
6.11k
    if (isl_tab_add_ineq(tab, bmap->ineq[i]) < 0)
2726
0
      return isl_stat_error;
2727
2.94k
2728
2.94k
  return isl_stat_ok;
2729
2.94k
}
2730
2731
/* Description of an integer division that is added
2732
 * during an expansion.
2733
 * "pos" is the position of the corresponding variable.
2734
 * "cst" indicates whether this integer division has a fixed value.
2735
 * "val" contains the fixed value, if the value is fixed.
2736
 */
2737
struct isl_expanded {
2738
  int pos;
2739
  isl_bool cst;
2740
  isl_int val;
2741
};
2742
2743
/* For each of the "n" integer division variables "expanded",
2744
 * if the variable has a fixed value, then add two inequality
2745
 * constraints expressing the fixed value.
2746
 * Otherwise, add the corresponding div constraints.
2747
 * The caller is responsible for removing the div constraints
2748
 * that it added for all these "n" integer divisions.
2749
 *
2750
 * The div constraints and the pair of inequality constraints
2751
 * forcing the fixed value cannot both be added for a given variable
2752
 * as the combination may render some of the original constraints redundant.
2753
 * These would then be ignored during the coalescing detection,
2754
 * while they could remain in the fused result.
2755
 *
2756
 * The two added inequality constraints are
2757
 *
2758
 *  -a + v >= 0
2759
 *  a - v >= 0
2760
 *
2761
 * with "a" the variable and "v" its fixed value.
2762
 * The facet corresponding to one of these two constraints is selected
2763
 * in the tableau to ensure that the pair of inequality constraints
2764
 * is treated as an equality constraint.
2765
 *
2766
 * The information in info->ineq is thrown away because it was
2767
 * computed in terms of div constraints, while some of those
2768
 * have now been replaced by these pairs of inequality constraints.
2769
 */
2770
static isl_stat fix_constant_divs(struct isl_coalesce_info *info,
2771
  int n, struct isl_expanded *expanded)
2772
138
{
2773
138
  unsigned o_div;
2774
138
  int i;
2775
138
  isl_vec *ineq;
2776
138
2777
138
  o_div = isl_basic_map_offset(info->bmap, isl_dim_div) - 1;
2778
138
  ineq = isl_vec_alloc(isl_tab_get_ctx(info->tab), 1 + info->tab->n_var);
2779
138
  if (!ineq)
2780
0
    return isl_stat_error;
2781
138
  isl_seq_clr(ineq->el + 1, info->tab->n_var);
2782
138
2783
364
  for (i = 0; i < n; 
++i226
) {
2784
226
    if (!expanded[i].cst) {
2785
32
      info->bmap = isl_basic_map_extend_constraints(
2786
32
            info->bmap, 0, 2);
2787
32
      if (isl_basic_map_add_div_constraints(info->bmap,
2788
32
            expanded[i].pos - o_div) < 0)
2789
0
        break;
2790
194
    } else {
2791
194
      isl_int_set_si(ineq->el[1 + expanded[i].pos], -1);
2792
194
      isl_int_set(ineq->el[0], expanded[i].val);
2793
194
      info->bmap = isl_basic_map_add_ineq(info->bmap,
2794
194
                ineq->el);
2795
194
      isl_int_set_si(ineq->el[1 + expanded[i].pos], 1);
2796
194
      isl_int_neg(ineq->el[0], expanded[i].val);
2797
194
      info->bmap = isl_basic_map_add_ineq(info->bmap,
2798
194
                ineq->el);
2799
194
      isl_int_set_si(ineq->el[1 + expanded[i].pos], 0);
2800
194
    }
2801
226
    if (copy_ineq(info->tab, info->bmap) < 0)
2802
0
      break;
2803
226
    if (expanded[i].cst &&
2804
226
        
isl_tab_select_facet(info->tab, info->tab->n_con - 1) < 0194
)
2805
0
      break;
2806
226
  }
2807
138
2808
138
  isl_vec_free(ineq);
2809
138
2810
138
  clear_status(info);
2811
138
  init_status(info);
2812
138
2813
138
  return i < n ? 
isl_stat_error0
: isl_stat_ok;
2814
138
}
2815
2816
/* Insert the "n" integer division variables "expanded"
2817
 * into info->tab and info->bmap and
2818
 * update info->ineq with respect to the redundant constraints
2819
 * in the resulting tableau.
2820
 * "bmap" contains the result of this insertion in info->bmap,
2821
 * while info->bmap is the original version
2822
 * of "bmap", i.e., the one that corresponds to the current
2823
 * state of info->tab.  The number of constraints in info->bmap
2824
 * is assumed to be the same as the number of constraints
2825
 * in info->tab.  This is required to be able to detect
2826
 * the extra constraints in "bmap".
2827
 *
2828
 * In particular, introduce extra variables corresponding
2829
 * to the extra integer divisions and add the div constraints
2830
 * that were added to "bmap" after info->tab was created
2831
 * from info->bmap.
2832
 * Furthermore, check if these extra integer divisions happen
2833
 * to attain a fixed integer value in info->tab.
2834
 * If so, replace the corresponding div constraints by pairs
2835
 * of inequality constraints that fix these
2836
 * integer divisions to their single integer values.
2837
 * Replace info->bmap by "bmap" to match the changes to info->tab.
2838
 * info->ineq was computed without a tableau and therefore
2839
 * does not take into account the redundant constraints
2840
 * in the tableau.  Mark them here.
2841
 * There is no need to check the newly added div constraints
2842
 * since they cannot be redundant.
2843
 * The redundancy check is not performed when constants have been discovered
2844
 * since info->ineq is completely thrown away in this case.
2845
 */
2846
static isl_stat tab_insert_divs(struct isl_coalesce_info *info,
2847
  int n, struct isl_expanded *expanded, __isl_take isl_basic_map *bmap)
2848
2.71k
{
2849
2.71k
  int i, n_ineq;
2850
2.71k
  unsigned n_eq;
2851
2.71k
  struct isl_tab_undo *snap;
2852
2.71k
  int any;
2853
2.71k
2854
2.71k
  if (!bmap)
2855
0
    return isl_stat_error;
2856
2.71k
  if (info->bmap->n_eq + info->bmap->n_ineq != info->tab->n_con)
2857
2.71k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_internal,
2858
2.71k
      "original tableau does not correspond "
2859
2.71k
      "to original basic map", goto error);
2860
2.71k
2861
2.71k
  if (isl_tab_extend_vars(info->tab, n) < 0)
2862
0
    goto error;
2863
2.71k
  if (isl_tab_extend_cons(info->tab, 2 * n) < 0)
2864
0
    goto error;
2865
2.71k
2866
5.54k
  
for (i = 0; 2.71k
i < n;
++i2.82k
) {
2867
2.82k
    if (isl_tab_insert_var(info->tab, expanded[i].pos) < 0)
2868
0
      goto error;
2869
2.82k
  }
2870
2.71k
2871
2.71k
  snap = isl_tab_snap(info->tab);
2872
2.71k
2873
2.71k
  n_ineq = info->tab->n_con - info->tab->n_eq;
2874
2.71k
  if (copy_ineq(info->tab, bmap) < 0)
2875
0
    goto error;
2876
2.71k
2877
2.71k
  isl_basic_map_free(info->bmap);
2878
2.71k
  info->bmap = bmap;
2879
2.71k
2880
2.71k
  any = 0;
2881
5.54k
  for (i = 0; i < n; 
++i2.82k
) {
2882
2.82k
    expanded[i].cst = isl_tab_is_constant(info->tab,
2883
2.82k
              expanded[i].pos, &expanded[i].val);
2884
2.82k
    if (expanded[i].cst < 0)
2885
0
      return isl_stat_error;
2886
2.82k
    if (expanded[i].cst)
2887
194
      any = 1;
2888
2.82k
  }
2889
2.71k
2890
2.71k
  if (any) {
2891
138
    if (isl_tab_rollback(info->tab, snap) < 0)
2892
0
      return isl_stat_error;
2893
138
    info->bmap = isl_basic_map_cow(info->bmap);
2894
138
    if (isl_basic_map_free_inequality(info->bmap, 2 * n) < 0)
2895
0
      return isl_stat_error;
2896
138
2897
138
    return fix_constant_divs(info, n, expanded);
2898
138
  }
2899
2.57k
2900
2.57k
  n_eq = info->bmap->n_eq;
2901
6.50k
  for (i = 0; i < n_ineq; 
++i3.92k
) {
2902
3.92k
    if (isl_tab_is_redundant(info->tab, n_eq + i))
2903
149
      info->ineq[i] = STATUS_REDUNDANT;
2904
3.92k
  }
2905
2.57k
2906
2.57k
  return isl_stat_ok;
2907
0
error:
2908
0
  isl_basic_map_free(bmap);
2909
0
  return isl_stat_error;
2910
2.57k
}
2911
2912
/* Expand info->tab and info->bmap in the same way "bmap" was expanded
2913
 * in isl_basic_map_expand_divs using the expansion "exp" and
2914
 * update info->ineq with respect to the redundant constraints
2915
 * in the resulting tableau. info->bmap is the original version
2916
 * of "bmap", i.e., the one that corresponds to the current
2917
 * state of info->tab.  The number of constraints in info->bmap
2918
 * is assumed to be the same as the number of constraints
2919
 * in info->tab.  This is required to be able to detect
2920
 * the extra constraints in "bmap".
2921
 *
2922
 * Extract the positions where extra local variables are introduced
2923
 * from "exp" and call tab_insert_divs.
2924
 */
2925
static isl_stat expand_tab(struct isl_coalesce_info *info, int *exp,
2926
  __isl_take isl_basic_map *bmap)
2927
2.71k
{
2928
2.71k
  isl_ctx *ctx;
2929
2.71k
  struct isl_expanded *expanded;
2930
2.71k
  int i, j, k, n;
2931
2.71k
  int extra_var;
2932
2.71k
  unsigned total, pos, n_div;
2933
2.71k
  isl_stat r;
2934
2.71k
2935
2.71k
  total = isl_basic_map_dim(bmap, isl_dim_all);
2936
2.71k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
2937
2.71k
  pos = total - n_div;
2938
2.71k
  extra_var = total - info->tab->n_var;
2939
2.71k
  n = n_div - extra_var;
2940
2.71k
2941
2.71k
  ctx = isl_basic_map_get_ctx(bmap);
2942
2.71k
  expanded = isl_calloc_array(ctx, struct isl_expanded, extra_var);
2943
2.71k
  if (extra_var && !expanded)
2944
0
    goto error;
2945
2.71k
2946
2.71k
  i = 0;
2947
2.71k
  k = 0;
2948
5.65k
  for (j = 0; j < n_div; 
++j2.94k
) {
2949
2.94k
    if (i < n && 
exp[i] == j195
) {
2950
111
      ++i;
2951
111
      continue;
2952
111
    }
2953
2.82k
    expanded[k++].pos = pos + j;
2954
2.82k
  }
2955
2.71k
2956
5.54k
  for (k = 0; k < extra_var; 
++k2.82k
)
2957
2.82k
    isl_int_init(expanded[k].val);
2958
2.71k
2959
2.71k
  r = tab_insert_divs(info, extra_var, expanded, bmap);
2960
2.71k
2961
5.54k
  for (k = 0; k < extra_var; 
++k2.82k
)
2962
2.82k
    isl_int_clear(expanded[k].val);
2963
2.71k
  free(expanded);
2964
2.71k
2965
2.71k
  return r;
2966
0
error:
2967
0
  isl_basic_map_free(bmap);
2968
0
  return isl_stat_error;
2969
2.71k
}
2970
2971
/* Check if the union of the basic maps represented by info[i] and info[j]
2972
 * can be represented by a single basic map,
2973
 * after expanding the divs of info[i] to match those of info[j].
2974
 * If so, replace the pair by the single basic map and return
2975
 * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
2976
 * Otherwise, return isl_change_none.
2977
 *
2978
 * The caller has already checked for info[j] being a subset of info[i].
2979
 * If some of the divs of info[j] are unknown, then the expanded info[i]
2980
 * will not have the corresponding div constraints.  The other patterns
2981
 * therefore cannot apply.  Skip the computation in this case.
2982
 *
2983
 * The expansion is performed using the divs "div" and expansion "exp"
2984
 * computed by the caller.
2985
 * info[i].bmap has already been expanded and the result is passed in
2986
 * as "bmap".
2987
 * The "eq" and "ineq" fields of info[i] reflect the status of
2988
 * the constraints of the expanded "bmap" with respect to info[j].tab.
2989
 * However, inequality constraints that are redundant in info[i].tab
2990
 * have not yet been marked as such because no tableau was available.
2991
 *
2992
 * Replace info[i].bmap by "bmap" and expand info[i].tab as well,
2993
 * updating info[i].ineq with respect to the redundant constraints.
2994
 * Then try and coalesce the expanded info[i] with info[j],
2995
 * reusing the information in info[i].eq and info[i].ineq.
2996
 * If this does not result in any coalescing or if it results in info[j]
2997
 * getting dropped (which should not happen in practice, since the case
2998
 * of info[j] being a subset of info[i] has already been checked by
2999
 * the caller), then revert info[i] to its original state.
3000
 */
3001
static enum isl_change coalesce_expand_tab_divs(__isl_take isl_basic_map *bmap,
3002
  int i, int j, struct isl_coalesce_info *info, __isl_keep isl_mat *div,
3003
  int *exp)
3004
2.72k
{
3005
2.72k
  isl_bool known;
3006
2.72k
  isl_basic_map *bmap_i;
3007
2.72k
  struct isl_tab_undo *snap;
3008
2.72k
  enum isl_change change = isl_change_none;
3009
2.72k
3010
2.72k
  known = isl_basic_map_divs_known(info[j].bmap);
3011
2.72k
  if (known < 0 || !known) {
3012
11
    clear_status(&info[i]);
3013
11
    isl_basic_map_free(bmap);
3014
11
    return known < 0 ? 
isl_change_error0
: isl_change_none;
3015
11
  }
3016
2.71k
3017
2.71k
  bmap_i = isl_basic_map_copy(info[i].bmap);
3018
2.71k
  snap = isl_tab_snap(info[i].tab);
3019
2.71k
  if (expand_tab(&info[i], exp, bmap) < 0)
3020
0
    change = isl_change_error;
3021
2.71k
3022
2.71k
  init_status(&info[j]);
3023
2.71k
  if (change == isl_change_none)
3024
2.71k
    change = coalesce_local_pair_reuse(i, j, info);
3025
0
  else
3026
0
    clear_status(&info[i]);
3027
2.71k
  if (change != isl_change_none && 
change != isl_change_drop_second701
) {
3028
701
    isl_basic_map_free(bmap_i);
3029
2.01k
  } else {
3030
2.01k
    isl_basic_map_free(info[i].bmap);
3031
2.01k
    info[i].bmap = bmap_i;
3032
2.01k
3033
2.01k
    if (isl_tab_rollback(info[i].tab, snap) < 0)
3034
0
      change = isl_change_error;
3035
2.01k
  }
3036
2.71k
3037
2.71k
  return change;
3038
2.71k
}
3039
3040
/* Check if the union of "bmap" and the basic map represented by info[j]
3041
 * can be represented by a single basic map,
3042
 * after expanding the divs of "bmap" to match those of info[j].
3043
 * If so, replace the pair by the single basic map and return
3044
 * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3045
 * Otherwise, return isl_change_none.
3046
 *
3047
 * In particular, check if the expanded "bmap" contains the basic map
3048
 * represented by the tableau info[j].tab.
3049
 * The expansion is performed using the divs "div" and expansion "exp"
3050
 * computed by the caller.
3051
 * Then we check if all constraints of the expanded "bmap" are valid for
3052
 * info[j].tab.
3053
 *
3054
 * If "i" is not equal to -1, then "bmap" is equal to info[i].bmap.
3055
 * In this case, the positions of the constraints of info[i].bmap
3056
 * with respect to the basic map represented by info[j] are stored
3057
 * in info[i].
3058
 *
3059
 * If the expanded "bmap" does not contain the basic map
3060
 * represented by the tableau info[j].tab and if "i" is not -1,
3061
 * i.e., if the original "bmap" is info[i].bmap, then expand info[i].tab
3062
 * as well and check if that results in coalescing.
3063
 */
3064
static enum isl_change coalesce_with_expanded_divs(
3065
  __isl_keep isl_basic_map *bmap, int i, int j,
3066
  struct isl_coalesce_info *info, __isl_keep isl_mat *div, int *exp)
3067
8.12k
{
3068
8.12k
  enum isl_change change = isl_change_none;
3069
8.12k
  struct isl_coalesce_info info_local, *info_i;
3070
8.12k
3071
8.12k
  info_i = i >= 0 ? 
&info[i]7.75k
:
&info_local367
;
3072
8.12k
  init_status(info_i);
3073
8.12k
  bmap = isl_basic_map_copy(bmap);
3074
8.12k
  bmap = isl_basic_map_expand_divs(bmap, isl_mat_copy(div), exp);
3075
8.12k
  bmap = isl_basic_map_mark_final(bmap);
3076
8.12k
3077
8.12k
  if (!bmap)
3078
0
    goto error;
3079
8.12k
3080
8.12k
  info_local.bmap = bmap;
3081
8.12k
  info_i->eq = eq_status_in(bmap, info[j].tab);
3082
8.12k
  if (bmap->n_eq && 
!info_i->eq1.17k
)
3083
0
    goto error;
3084
8.12k
  if (any_eq(info_i, STATUS_ERROR))
3085
0
    goto error;
3086
8.12k
  if (any_eq(info_i, STATUS_SEPARATE))
3087
413
    goto done;
3088
7.71k
3089
7.71k
  info_i->ineq = ineq_status_in(bmap, NULL, info[j].tab);
3090
7.71k
  if (bmap->n_ineq && 
!info_i->ineq7.41k
)
3091
0
    goto error;
3092
7.71k
  if (any_ineq(info_i, STATUS_ERROR))
3093
0
    goto error;
3094
7.71k
  if (any_ineq(info_i, STATUS_SEPARATE))
3095
2.21k
    goto done;
3096
5.49k
3097
5.49k
  if (all(info_i->eq, 2 * bmap->n_eq, STATUS_VALID) &&
3098
5.49k
      
all(info_i->ineq, bmap->n_ineq, 4.92k
STATUS_VALID4.92k
)) {
3099
2.40k
    drop(&info[j]);
3100
2.40k
    change = isl_change_drop_second;
3101
2.40k
  }
3102
5.49k
3103
5.49k
  if (change == isl_change_none && 
i != -13.08k
)
3104
2.72k
    return coalesce_expand_tab_divs(bmap, i, j, info, div, exp);
3105
5.39k
3106
5.39k
done:
3107
5.39k
  isl_basic_map_free(bmap);
3108
5.39k
  clear_status(info_i);
3109
5.39k
  return change;
3110
0
error:
3111
0
  isl_basic_map_free(bmap);
3112
0
  clear_status(info_i);
3113
0
  return isl_change_error;
3114
5.49k
}
3115
3116
/* Check if the union of "bmap_i" and the basic map represented by info[j]
3117
 * can be represented by a single basic map,
3118
 * after aligning the divs of "bmap_i" to match those of info[j].
3119
 * If so, replace the pair by the single basic map and return
3120
 * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3121
 * Otherwise, return isl_change_none.
3122
 *
3123
 * In particular, check if "bmap_i" contains the basic map represented by
3124
 * info[j] after aligning the divs of "bmap_i" to those of info[j].
3125
 * Note that this can only succeed if the number of divs of "bmap_i"
3126
 * is smaller than (or equal to) the number of divs of info[j].
3127
 *
3128
 * We first check if the divs of "bmap_i" are all known and form a subset
3129
 * of those of info[j].bmap.  If so, we pass control over to
3130
 * coalesce_with_expanded_divs.
3131
 *
3132
 * If "i" is not equal to -1, then "bmap" is equal to info[i].bmap.
3133
 */
3134
static enum isl_change coalesce_after_aligning_divs(
3135
  __isl_keep isl_basic_map *bmap_i, int i, int j,
3136
  struct isl_coalesce_info *info)
3137
8.29k
{
3138
8.29k
  isl_bool known;
3139
8.29k
  isl_mat *div_i, *div_j, *div;
3140
8.29k
  int *exp1 = NULL;
3141
8.29k
  int *exp2 = NULL;
3142
8.29k
  isl_ctx *ctx;
3143
8.29k
  enum isl_change change;
3144
8.29k
3145
8.29k
  known = isl_basic_map_divs_known(bmap_i);
3146
8.29k
  if (known < 0)
3147
0
    return isl_change_error;
3148
8.29k
  if (!known)
3149
0
    return isl_change_none;
3150
8.29k
3151
8.29k
  ctx = isl_basic_map_get_ctx(bmap_i);
3152
8.29k
3153
8.29k
  div_i = isl_basic_map_get_divs(bmap_i);
3154
8.29k
  div_j = isl_basic_map_get_divs(info[j].bmap);
3155
8.29k
3156
8.29k
  if (!div_i || !div_j)
3157
0
    goto error;
3158
8.29k
3159
8.29k
  exp1 = isl_alloc_array(ctx, int, div_i->n_row);
3160
8.29k
  exp2 = isl_alloc_array(ctx, int, div_j->n_row);
3161
8.29k
  if ((div_i->n_row && 
!exp1363
) || (div_j->n_row &&
!exp27.99k
))
3162
0
    goto error;
3163
8.29k
3164
8.29k
  div = isl_merge_divs(div_i, div_j, exp1, exp2);
3165
8.29k
  if (!div)
3166
0
    goto error;
3167
8.29k
3168
8.29k
  if (div->n_row == div_j->n_row)
3169
8.12k
    change = coalesce_with_expanded_divs(bmap_i,
3170
8.12k
              i, j, info, div, exp1);
3171
171
  else
3172
171
    change = isl_change_none;
3173
8.29k
3174
8.29k
  isl_mat_free(div);
3175
8.29k
3176
8.29k
  isl_mat_free(div_i);
3177
8.29k
  isl_mat_free(div_j);
3178
8.29k
3179
8.29k
  free(exp2);
3180
8.29k
  free(exp1);
3181
8.29k
3182
8.29k
  return change;
3183
0
error:
3184
0
  isl_mat_free(div_i);
3185
0
  isl_mat_free(div_j);
3186
0
  free(exp1);
3187
0
  free(exp2);
3188
0
  return isl_change_error;
3189
8.29k
}
3190
3191
/* Check if basic map "j" is a subset of basic map "i" after
3192
 * exploiting the extra equalities of "j" to simplify the divs of "i".
3193
 * If so, remove basic map "j" and return isl_change_drop_second.
3194
 *
3195
 * If "j" does not have any equalities or if they are the same
3196
 * as those of "i", then we cannot exploit them to simplify the divs.
3197
 * Similarly, if there are no divs in "i", then they cannot be simplified.
3198
 * If, on the other hand, the affine hulls of "i" and "j" do not intersect,
3199
 * then "j" cannot be a subset of "i".
3200
 *
3201
 * Otherwise, we intersect "i" with the affine hull of "j" and then
3202
 * check if "j" is a subset of the result after aligning the divs.
3203
 * If so, then "j" is definitely a subset of "i" and can be removed.
3204
 * Note that if after intersection with the affine hull of "j".
3205
 * "i" still has more divs than "j", then there is no way we can
3206
 * align the divs of "i" to those of "j".
3207
 */
3208
static enum isl_change coalesce_subset_with_equalities(int i, int j,
3209
  struct isl_coalesce_info *info)
3210
9.96k
{
3211
9.96k
  isl_basic_map *hull_i, *hull_j, *bmap_i;
3212
9.96k
  int equal, empty;
3213
9.96k
  enum isl_change change;
3214
9.96k
3215
9.96k
  if (info[j].bmap->n_eq == 0)
3216
8.30k
    return isl_change_none;
3217
1.65k
  if (info[i].bmap->n_div == 0)
3218
564
    return isl_change_none;
3219
1.09k
3220
1.09k
  hull_i = isl_basic_map_copy(info[i].bmap);
3221
1.09k
  hull_i = isl_basic_map_plain_affine_hull(hull_i);
3222
1.09k
  hull_j = isl_basic_map_copy(info[j].bmap);
3223
1.09k
  hull_j = isl_basic_map_plain_affine_hull(hull_j);
3224
1.09k
3225
1.09k
  hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i));
3226
1.09k
  equal = isl_basic_map_plain_is_equal(hull_i, hull_j);
3227
1.09k
  empty = isl_basic_map_plain_is_empty(hull_j);
3228
1.09k
  isl_basic_map_free(hull_i);
3229
1.09k
3230
1.09k
  if (equal < 0 || equal || 
empty < 0898
||
empty898
) {
3231
520
    isl_basic_map_free(hull_j);
3232
520
    if (equal < 0 || empty < 0)
3233
0
      return isl_change_error;
3234
520
    return isl_change_none;
3235
520
  }
3236
575
3237
575
  bmap_i = isl_basic_map_copy(info[i].bmap);
3238
575
  bmap_i = isl_basic_map_intersect(bmap_i, hull_j);
3239
575
  if (!bmap_i)
3240
0
    return isl_change_error;
3241
575
3242
575
  if (bmap_i->n_div > info[j].bmap->n_div) {
3243
128
    isl_basic_map_free(bmap_i);
3244
128
    return isl_change_none;
3245
128
  }
3246
447
3247
447
  change = coalesce_after_aligning_divs(bmap_i, -1, j, info);
3248
447
3249
447
  isl_basic_map_free(bmap_i);
3250
447
3251
447
  return change;
3252
447
}
3253
3254
/* Check if the union of and the basic maps represented by info[i] and info[j]
3255
 * can be represented by a single basic map, by aligning or equating
3256
 * their integer divisions.
3257
 * If so, replace the pair by the single basic map and return
3258
 * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3259
 * Otherwise, return isl_change_none.
3260
 *
3261
 * Note that we only perform any test if the number of divs is different
3262
 * in the two basic maps.  In case the number of divs is the same,
3263
 * we have already established that the divs are different
3264
 * in the two basic maps.
3265
 * In particular, if the number of divs of basic map i is smaller than
3266
 * the number of divs of basic map j, then we check if j is a subset of i
3267
 * and vice versa.
3268
 */
3269
static enum isl_change coalesce_divs(int i, int j,
3270
  struct isl_coalesce_info *info)
3271
8.08k
{
3272
8.08k
  enum isl_change change = isl_change_none;
3273
8.08k
3274
8.08k
  if (info[i].bmap->n_div < info[j].bmap->n_div)
3275
7.14k
    change = coalesce_after_aligning_divs(info[i].bmap, i, j, info);
3276
8.08k
  if (change != isl_change_none)
3277
3.05k
    return change;
3278
5.03k
3279
5.03k
  if (info[j].bmap->n_div < info[i].bmap->n_div)
3280
701
    change = coalesce_after_aligning_divs(info[j].bmap, j, i, info);
3281
5.03k
  if (change != isl_change_none)
3282
52
    return invert_change(change);
3283
4.98k
3284
4.98k
  change = coalesce_subset_with_equalities(i, j, info);
3285
4.98k
  if (change != isl_change_none)
3286
3
    return change;
3287
4.98k
3288
4.98k
  change = coalesce_subset_with_equalities(j, i, info);
3289
4.98k
  if (change != isl_change_none)
3290
0
    return invert_change(change);
3291
4.98k
3292
4.98k
  return isl_change_none;
3293
4.98k
}
3294
3295
/* Does "bmap" involve any divs that themselves refer to divs?
3296
 */
3297
static isl_bool has_nested_div(__isl_keep isl_basic_map *bmap)
3298
9.88k
{
3299
9.88k
  int i;
3300
9.88k
  unsigned total;
3301
9.88k
  unsigned n_div;
3302
9.88k
3303
9.88k
  total = isl_basic_map_dim(bmap, isl_dim_all);
3304
9.88k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
3305
9.88k
  total -= n_div;
3306
9.88k
3307
16.3k
  for (i = 0; i < n_div; 
++i6.44k
)
3308
6.46k
    if (isl_seq_first_non_zero(bmap->div[i] + 2 + total,
3309
6.46k
              n_div) != -1)
3310
28
      return isl_bool_true;
3311
9.88k
3312
9.88k
  
return isl_bool_false9.85k
;
3313
9.88k
}
3314
3315
/* Return a list of affine expressions, one for each integer division
3316
 * in "bmap_i".  For each integer division that also appears in "bmap_j",
3317
 * the affine expression is set to NaN.  The number of NaNs in the list
3318
 * is equal to the number of integer divisions in "bmap_j".
3319
 * For the other integer divisions of "bmap_i", the corresponding
3320
 * element in the list is a purely affine expression equal to the integer
3321
 * division in "hull".
3322
 * If no such list can be constructed, then the number of elements
3323
 * in the returned list is smaller than the number of integer divisions
3324
 * in "bmap_i".
3325
 */
3326
static __isl_give isl_aff_list *set_up_substitutions(
3327
  __isl_keep isl_basic_map *bmap_i, __isl_keep isl_basic_map *bmap_j,
3328
  __isl_take isl_basic_map *hull)
3329
412
{
3330
412
  unsigned n_div_i, n_div_j, total;
3331
412
  isl_ctx *ctx;
3332
412
  isl_local_space *ls;
3333
412
  isl_basic_set *wrap_hull;
3334
412
  isl_aff *aff_nan;
3335
412
  isl_aff_list *list;
3336
412
  int i, j;
3337
412
3338
412
  if (!hull)
3339
0
    return NULL;
3340
412
3341
412
  ctx = isl_basic_map_get_ctx(hull);
3342
412
3343
412
  n_div_i = isl_basic_map_dim(bmap_i, isl_dim_div);
3344
412
  n_div_j = isl_basic_map_dim(bmap_j, isl_dim_div);
3345
412
  total = isl_basic_map_total_dim(bmap_i) - n_div_i;
3346
412
3347
412
  ls = isl_basic_map_get_local_space(bmap_i);
3348
412
  ls = isl_local_space_wrap(ls);
3349
412
  wrap_hull = isl_basic_map_wrap(hull);
3350
412
3351
412
  aff_nan = isl_aff_nan_on_domain(isl_local_space_copy(ls));
3352
412
  list = isl_aff_list_alloc(ctx, n_div_i);
3353
412
3354
412
  j = 0;
3355
725
  for (i = 0; i < n_div_i; 
++i313
) {
3356
496
    isl_aff *aff;
3357
496
3358
496
    if (j < n_div_j &&
3359
496
        isl_basic_map_equal_div_expr_part(bmap_i, i, bmap_j, j,
3360
50
                0, 2 + total)) {
3361
28
      ++j;
3362
28
      list = isl_aff_list_add(list, isl_aff_copy(aff_nan));
3363
28
      continue;
3364
28
    }
3365
468
    if (n_div_i - i <= n_div_j - j)
3366
0
      break;
3367
468
3368
468
    aff = isl_local_space_get_div(ls, i);
3369
468
    aff = isl_aff_substitute_equalities(aff,
3370
468
            isl_basic_set_copy(wrap_hull));
3371
468
    aff = isl_aff_floor(aff);
3372
468
    if (!aff)
3373
0
      goto error;
3374
468
    if (isl_aff_dim(aff, isl_dim_div) != 0) {
3375
183
      isl_aff_free(aff);
3376
183
      break;
3377
183
    }
3378
285
3379
285
    list = isl_aff_list_add(list, aff);
3380
285
  }
3381
412
3382
412
  isl_aff_free(aff_nan);
3383
412
  isl_local_space_free(ls);
3384
412
  isl_basic_set_free(wrap_hull);
3385
412
3386
412
  return list;
3387
0
error:
3388
0
  isl_aff_free(aff_nan);
3389
0
  isl_local_space_free(ls);
3390
0
  isl_basic_set_free(wrap_hull);
3391
0
  isl_aff_list_free(list);
3392
0
  return NULL;
3393
412
}
3394
3395
/* Add variables to info->bmap and info->tab corresponding to the elements
3396
 * in "list" that are not set to NaN.
3397
 * "extra_var" is the number of these elements.
3398
 * "dim" is the offset in the variables of "tab" where we should
3399
 * start considering the elements in "list".
3400
 * When this function returns, the total number of variables in "tab"
3401
 * is equal to "dim" plus the number of elements in "list".
3402
 *
3403
 * The newly added existentially quantified variables are not given
3404
 * an explicit representation because the corresponding div constraints
3405
 * do not appear in info->bmap.  These constraints are not added
3406
 * to info->bmap because for internal consistency, they would need to
3407
 * be added to info->tab as well, where they could combine with the equality
3408
 * that is added later to result in constraints that do not hold
3409
 * in the original input.
3410
 */
3411
static isl_stat add_sub_vars(struct isl_coalesce_info *info,
3412
  __isl_keep isl_aff_list *list, int dim, int extra_var)
3413
229
{
3414
229
  int i, j, n, d;
3415
229
  isl_space *space;
3416
229
3417
229
  space = isl_basic_map_get_space(info->bmap);
3418
229
  info->bmap = isl_basic_map_cow(info->bmap);
3419
229
  info->bmap = isl_basic_map_extend_space(info->bmap, space,
3420
229
            extra_var, 0, 0);
3421
229
  if (!info->bmap)
3422
0
    return isl_stat_error;
3423
229
  n = isl_aff_list_n_aff(list);
3424
511
  for (i = 0; i < n; 
++i282
) {
3425
282
    int is_nan;
3426
282
    isl_aff *aff;
3427
282
3428
282
    aff = isl_aff_list_get_aff(list, i);
3429
282
    is_nan = isl_aff_is_nan(aff);
3430
282
    isl_aff_free(aff);
3431
282
    if (is_nan < 0)
3432
0
      return isl_stat_error;
3433
282
    if (is_nan)
3434
15
      continue;
3435
267
3436
267
    if (isl_tab_insert_var(info->tab, dim + i) < 0)
3437
0
      return isl_stat_error;
3438
267
    d = isl_basic_map_alloc_div(info->bmap);
3439
267
    if (d < 0)
3440
0
      return isl_stat_error;
3441
267
    info->bmap = isl_basic_map_mark_div_unknown(info->bmap, d);
3442
267
    if (!info->bmap)
3443
0
      return isl_stat_error;
3444
281
    
for (j = d; 267
j > i;
--j14
)
3445
14
      isl_basic_map_swap_div(info->bmap, j - 1, j);
3446
267
  }
3447
229
3448
229
  return isl_stat_ok;
3449
229
}
3450
3451
/* For each element in "list" that is not set to NaN, fix the corresponding
3452
 * variable in "tab" to the purely affine expression defined by the element.
3453
 * "dim" is the offset in the variables of "tab" where we should
3454
 * start considering the elements in "list".
3455
 *
3456
 * This function assumes that a sufficient number of rows and
3457
 * elements in the constraint array are available in the tableau.
3458
 */
3459
static int add_sub_equalities(struct isl_tab *tab,
3460
  __isl_keep isl_aff_list *list, int dim)
3461
229
{
3462
229
  int i, n;
3463
229
  isl_ctx *ctx;
3464
229
  isl_vec *sub;
3465
229
  isl_aff *aff;
3466
229
3467
229
  n = isl_aff_list_n_aff(list);
3468
229
3469
229
  ctx = isl_tab_get_ctx(tab);
3470
229
  sub = isl_vec_alloc(ctx, 1 + dim + n);
3471
229
  if (!sub)
3472
0
    return -1;
3473
229
  isl_seq_clr(sub->el + 1 + dim, n);
3474
229
3475
511
  for (i = 0; i < n; 
++i282
) {
3476
282
    aff = isl_aff_list_get_aff(list, i);
3477
282
    if (!aff)
3478
0
      goto error;
3479
282
    if (isl_aff_is_nan(aff)) {
3480
15
      isl_aff_free(aff);
3481
15
      continue;
3482
15
    }
3483
267
    isl_seq_cpy(sub->el, aff->v->el + 1, 1 + dim);
3484
267
    isl_int_neg(sub->el[1 + dim + i], aff->v->el[0]);
3485
267
    if (isl_tab_add_eq(tab, sub->el) < 0)
3486
0
      goto error;
3487
267
    isl_int_set_si(sub->el[1 + dim + i], 0);
3488
267
    isl_aff_free(aff);
3489
267
  }
3490
229
3491
229
  isl_vec_free(sub);
3492
229
  return 0;
3493
0
error:
3494
0
  isl_aff_free(aff);
3495
0
  isl_vec_free(sub);
3496
0
  return -1;
3497
229
}
3498
3499
/* Add variables to info->tab and info->bmap corresponding to the elements
3500
 * in "list" that are not set to NaN.  The value of the added variable
3501
 * in info->tab is fixed to the purely affine expression defined by the element.
3502
 * "dim" is the offset in the variables of info->tab where we should
3503
 * start considering the elements in "list".
3504
 * When this function returns, the total number of variables in info->tab
3505
 * is equal to "dim" plus the number of elements in "list".
3506
 */
3507
static int add_subs(struct isl_coalesce_info *info,
3508
  __isl_keep isl_aff_list *list, int dim)
3509
229
{
3510
229
  int extra_var;
3511
229
  int n;
3512
229
3513
229
  if (!list)
3514
0
    return -1;
3515
229
3516
229
  n = isl_aff_list_n_aff(list);
3517
229
  extra_var = n - (info->tab->n_var - dim);
3518
229
3519
229
  if (isl_tab_extend_vars(info->tab, extra_var) < 0)
3520
0
    return -1;
3521
229
  if (isl_tab_extend_cons(info->tab, 2 * extra_var) < 0)
3522
0
    return -1;
3523
229
  if (add_sub_vars(info, list, dim, extra_var) < 0)
3524
0
    return -1;
3525
229
3526
229
  return add_sub_equalities(info->tab, list, dim);
3527
229
}
3528
3529
/* Coalesce basic map "j" into basic map "i" after adding the extra integer
3530
 * divisions in "i" but not in "j" to basic map "j", with values
3531
 * specified by "list".  The total number of elements in "list"
3532
 * is equal to the number of integer divisions in "i", while the number
3533
 * of NaN elements in the list is equal to the number of integer divisions
3534
 * in "j".
3535
 *
3536
 * If no coalescing can be performed, then we need to revert basic map "j"
3537
 * to its original state.  We do the same if basic map "i" gets dropped
3538
 * during the coalescing, even though this should not happen in practice
3539
 * since we have already checked for "j" being a subset of "i"
3540
 * before we reach this stage.
3541
 */
3542
static enum isl_change coalesce_with_subs(int i, int j,
3543
  struct isl_coalesce_info *info, __isl_keep isl_aff_list *list)
3544
229
{
3545
229
  isl_basic_map *bmap_j;
3546
229
  struct isl_tab_undo *snap;
3547
229
  unsigned dim;
3548
229
  enum isl_change change;
3549
229
3550
229
  bmap_j = isl_basic_map_copy(info[j].bmap);
3551
229
  snap = isl_tab_snap(info[j].tab);
3552
229
3553
229
  dim = isl_basic_map_dim(bmap_j, isl_dim_all);
3554
229
  dim -= isl_basic_map_dim(bmap_j, isl_dim_div);
3555
229
  if (add_subs(&info[j], list, dim) < 0)
3556
0
    goto error;
3557
229
3558
229
  change = coalesce_local_pair(i, j, info);
3559
229
  if (change != isl_change_none && 
change != isl_change_drop_first18
) {
3560
18
    isl_basic_map_free(bmap_j);
3561
211
  } else {
3562
211
    isl_basic_map_free(info[j].bmap);
3563
211
    info[j].bmap = bmap_j;
3564
211
3565
211
    if (isl_tab_rollback(info[j].tab, snap) < 0)
3566
0
      return isl_change_error;
3567
229
  }
3568
229
3569
229
  return change;
3570
0
error:
3571
0
  isl_basic_map_free(bmap_j);
3572
0
  return isl_change_error;
3573
229
}
3574
3575
/* Check if we can coalesce basic map "j" into basic map "i" after copying
3576
 * those extra integer divisions in "i" that can be simplified away
3577
 * using the extra equalities in "j".
3578
 * All divs are assumed to be known and not contain any nested divs.
3579
 *
3580
 * We first check if there are any extra equalities in "j" that we
3581
 * can exploit.  Then we check if every integer division in "i"
3582
 * either already appears in "j" or can be simplified using the
3583
 * extra equalities to a purely affine expression.
3584
 * If these tests succeed, then we try to coalesce the two basic maps
3585
 * by introducing extra dimensions in "j" corresponding to
3586
 * the extra integer divsisions "i" fixed to the corresponding
3587
 * purely affine expression.
3588
 */
3589
static enum isl_change check_coalesce_into_eq(int i, int j,
3590
  struct isl_coalesce_info *info)
3591
9.82k
{
3592
9.82k
  unsigned n_div_i, n_div_j;
3593
9.82k
  isl_basic_map *hull_i, *hull_j;
3594
9.82k
  int equal, empty;
3595
9.82k
  isl_aff_list *list;
3596
9.82k
  enum isl_change change;
3597
9.82k
3598
9.82k
  n_div_i = isl_basic_map_dim(info[i].bmap, isl_dim_div);
3599
9.82k
  n_div_j = isl_basic_map_dim(info[j].bmap, isl_dim_div);
3600
9.82k
  if (n_div_i <= n_div_j)
3601
5.14k
    return isl_change_none;
3602
4.68k
  if (info[j].bmap->n_eq == 0)
3603
3.95k
    return isl_change_none;
3604
727
3605
727
  hull_i = isl_basic_map_copy(info[i].bmap);
3606
727
  hull_i = isl_basic_map_plain_affine_hull(hull_i);
3607
727
  hull_j = isl_basic_map_copy(info[j].bmap);
3608
727
  hull_j = isl_basic_map_plain_affine_hull(hull_j);
3609
727
3610
727
  hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i));
3611
727
  equal = isl_basic_map_plain_is_equal(hull_i, hull_j);
3612
727
  empty = isl_basic_map_plain_is_empty(hull_j);
3613
727
  isl_basic_map_free(hull_i);
3614
727
3615
727
  if (equal < 0 || empty < 0)
3616
0
    goto error;
3617
727
  if (equal || 
empty635
) {
3618
315
    isl_basic_map_free(hull_j);
3619
315
    return isl_change_none;
3620
315
  }
3621
412
3622
412
  list = set_up_substitutions(info[i].bmap, info[j].bmap, hull_j);
3623
412
  if (!list)
3624
0
    return isl_change_error;
3625
412
  if (isl_aff_list_n_aff(list) < n_div_i)
3626
183
    change = isl_change_none;
3627
229
  else
3628
229
    change = coalesce_with_subs(i, j, info, list);
3629
412
3630
412
  isl_aff_list_free(list);
3631
412
3632
412
  return change;
3633
0
error:
3634
0
  isl_basic_map_free(hull_j);
3635
0
  return isl_change_error;
3636
412
}
3637
3638
/* Check if we can coalesce basic maps "i" and "j" after copying
3639
 * those extra integer divisions in one of the basic maps that can
3640
 * be simplified away using the extra equalities in the other basic map.
3641
 * We require all divs to be known in both basic maps.
3642
 * Furthermore, to simplify the comparison of div expressions,
3643
 * we do not allow any nested integer divisions.
3644
 */
3645
static enum isl_change check_coalesce_eq(int i, int j,
3646
  struct isl_coalesce_info *info)
3647
4.98k
{
3648
4.98k
  isl_bool known, nested;
3649
4.98k
  enum isl_change change;
3650
4.98k
3651
4.98k
  known = isl_basic_map_divs_known(info[i].bmap);
3652
4.98k
  if (known < 0 || !known)
3653
26
    return known < 0 ? 
isl_change_error0
: isl_change_none;
3654
4.95k
  known = isl_basic_map_divs_known(info[j].bmap);
3655
4.95k
  if (known < 0 || !known)
3656
9
    return known < 0 ? 
isl_change_error0
: isl_change_none;
3657
4.94k
  nested = has_nested_div(info[i].bmap);
3658
4.94k
  if (nested < 0 || nested)
3659
3
    return nested < 0 ? 
isl_change_error0
: isl_change_none;
3660
4.94k
  nested = has_nested_div(info[j].bmap);
3661
4.94k
  if (nested < 0 || nested)
3662
25
    return nested < 0 ? 
isl_change_error0
: isl_change_none;
3663
4.91k
3664
4.91k
  change = check_coalesce_into_eq(i, j, info);
3665
4.91k
  if (change != isl_change_none)
3666
7
    return change;
3667
4.91k
  change = check_coalesce_into_eq(j, i, info);
3668
4.91k
  if (change != isl_change_none)
3669
11
    return invert_change(change);
3670
4.89k
3671
4.89k
  return isl_change_none;
3672
4.89k
}
3673
3674
/* Check if the union of the given pair of basic maps
3675
 * can be represented by a single basic map.
3676
 * If so, replace the pair by the single basic map and return
3677
 * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3678
 * Otherwise, return isl_change_none.
3679
 *
3680
 * We first check if the two basic maps live in the same local space,
3681
 * after aligning the divs that differ by only an integer constant.
3682
 * If so, we do the complete check.  Otherwise, we check if they have
3683
 * the same number of integer divisions and can be coalesced, if one is
3684
 * an obvious subset of the other or if the extra integer divisions
3685
 * of one basic map can be simplified away using the extra equalities
3686
 * of the other basic map.
3687
 *
3688
 * Note that trying to coalesce pairs of disjuncts with the same
3689
 * number, but different local variables may drop the explicit
3690
 * representation of some of these local variables.
3691
 * This operation is therefore not performed when
3692
 * the "coalesce_preserve_locals" option is set.
3693
 */
3694
static enum isl_change coalesce_pair(int i, int j,
3695
  struct isl_coalesce_info *info)
3696
66.2k
{
3697
66.2k
  int preserve;
3698
66.2k
  isl_bool same;
3699
66.2k
  enum isl_change change;
3700
66.2k
  isl_ctx *ctx;
3701
66.2k
3702
66.2k
  if (harmonize_divs(&info[i], &info[j]) < 0)
3703
0
    return isl_change_error;
3704
66.2k
  same = same_divs(info[i].bmap, info[j].bmap);
3705
66.2k
  if (same < 0)
3706
0
    return isl_change_error;
3707
66.2k
  if (same)
3708
58.1k
    return coalesce_local_pair(i, j, info);
3709
8.09k
3710
8.09k
  ctx = isl_basic_map_get_ctx(info[i].bmap);
3711
8.09k
  preserve = isl_options_get_coalesce_preserve_locals(ctx);
3712
8.09k
  if (!preserve && 
info[i].bmap->n_div == info[j].bmap->n_div8.08k
) {
3713
246
    change = coalesce_local_pair(i, j, info);
3714
246
    if (change != isl_change_none)
3715
4
      return change;
3716
8.08k
  }
3717
8.08k
3718
8.08k
  change = coalesce_divs(i, j, info);
3719
8.08k
  if (change != isl_change_none)
3720
3.10k
    return change;
3721
4.98k
3722
4.98k
  return check_coalesce_eq(i, j, info);
3723
4.98k
}
3724
3725
/* Return the maximum of "a" and "b".
3726
 */
3727
static int isl_max(int a, int b)
3728
112k
{
3729
112k
  return a > b ? 
a58.3k
:
b53.9k
;
3730
112k
}
3731
3732
/* Pairwise coalesce the basic maps in the range [start1, end1[ of "info"
3733
 * with those in the range [start2, end2[, skipping basic maps
3734
 * that have been removed (either before or within this function).
3735
 *
3736
 * For each basic map i in the first range, we check if it can be coalesced
3737
 * with respect to any previously considered basic map j in the second range.
3738
 * If i gets dropped (because it was a subset of some j), then
3739
 * we can move on to the next basic map.
3740
 * If j gets dropped, we need to continue checking against the other
3741
 * previously considered basic maps.
3742
 * If the two basic maps got fused, then we recheck the fused basic map
3743
 * against the previously considered basic maps, starting at i + 1
3744
 * (even if start2 is greater than i + 1).
3745
 */
3746
static int coalesce_range(isl_ctx *ctx, struct isl_coalesce_info *info,
3747
  int start1, int end1, int start2, int end2)
3748
82.4k
{
3749
82.4k
  int i, j;
3750
82.4k
3751
199k
  for (i = end1 - 1; i >= start1; 
--i116k
) {
3752
116k
    if (info[i].removed)
3753
4.58k
      continue;
3754
192k
    
for (j = isl_max(i + 1, start2); 112k
j < end2;
++j80.3k
) {
3755
80.3k
      enum isl_change changed;
3756
80.3k
3757
80.3k
      if (info[j].removed)
3758
14.0k
        continue;
3759
66.2k
      if (info[i].removed)
3760
66.2k
        
isl_die0
(ctx, isl_error_internal,
3761
66.2k
          "basic map unexpectedly removed",
3762
66.2k
          return -1);
3763
66.2k
      changed = coalesce_pair(i, j, info);
3764
66.2k
      switch (changed) {
3765
66.2k
      case isl_change_error:
3766
0
        return -1;
3767
66.2k
      case isl_change_none:
3768
61.4k
      case isl_change_drop_second:
3769
61.4k
        continue;
3770
61.4k
      case isl_change_drop_first:
3771
3.01k
        j = end2;
3772
3.01k
        break;
3773
61.4k
      case isl_change_fuse:
3774
1.83k
        j = i;
3775
1.83k
        break;
3776
66.2k
      }
3777
66.2k
    }
3778
112k
  }
3779
82.4k
3780
82.4k
  return 0;
3781
82.4k
}
3782
3783
/* Pairwise coalesce the basic maps described by the "n" elements of "info".
3784
 *
3785
 * We consider groups of basic maps that live in the same apparent
3786
 * affine hull and we first coalesce within such a group before we
3787
 * coalesce the elements in the group with elements of previously
3788
 * considered groups.  If a fuse happens during the second phase,
3789
 * then we also reconsider the elements within the group.
3790
 */
3791
static int coalesce(isl_ctx *ctx, int n, struct isl_coalesce_info *info)
3792
24.3k
{
3793
24.3k
  int start, end;
3794
24.3k
3795
65.5k
  for (end = n; end > 0; 
end = start41.2k
) {
3796
41.2k
    start = end - 1;
3797
58.4k
    while (start >= 1 &&
3798
58.4k
        
info[start - 1].hull_hash == info[start].hull_hash34.0k
)
3799
17.2k
      start--;
3800
41.2k
    if (coalesce_range(ctx, info, start, end, start, end) < 0)
3801
0
      return -1;
3802
41.2k
    if (coalesce_range(ctx, info, start, end, end, n) < 0)
3803
0
      return -1;
3804
41.2k
  }
3805
24.3k
3806
24.3k
  return 0;
3807
24.3k
}
3808
3809
/* Update the basic maps in "map" based on the information in "info".
3810
 * In particular, remove the basic maps that have been marked removed and
3811
 * update the others based on the information in the corresponding tableau.
3812
 * Since we detected implicit equalities without calling
3813
 * isl_basic_map_gauss, we need to do it now.
3814
 * Also call isl_basic_map_simplify if we may have lost the definition
3815
 * of one or more integer divisions.
3816
 */
3817
static __isl_give isl_map *update_basic_maps(__isl_take isl_map *map,
3818
  int n, struct isl_coalesce_info *info)
3819
24.3k
{
3820
24.3k
  int i;
3821
24.3k
3822
24.3k
  if (!map)
3823
0
    return NULL;
3824
24.3k
3825
82.8k
  
for (i = n - 1; 24.3k
i >= 0;
--i58.4k
) {
3826
58.4k
    if (info[i].removed) {
3827
10.2k
      isl_basic_map_free(map->p[i]);
3828
10.2k
      if (i != map->n - 1)
3829
3.81k
        map->p[i] = map->p[map->n - 1];
3830
10.2k
      map->n--;
3831
10.2k
      continue;
3832
10.2k
    }
3833
48.2k
3834
48.2k
    info[i].bmap = isl_basic_map_update_from_tab(info[i].bmap,
3835
48.2k
              info[i].tab);
3836
48.2k
    info[i].bmap = isl_basic_map_gauss(info[i].bmap, NULL);
3837
48.2k
    if (info[i].simplify)
3838
22
      info[i].bmap = isl_basic_map_simplify(info[i].bmap);
3839
48.2k
    info[i].bmap = isl_basic_map_finalize(info[i].bmap);
3840
48.2k
    if (!info[i].bmap)
3841
0
      return isl_map_free(map);
3842
48.2k
    ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT);
3843
48.2k
    ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT);
3844
48.2k
    isl_basic_map_free(map->p[i]);
3845
48.2k
    map->p[i] = info[i].bmap;
3846
48.2k
    info[i].bmap = NULL;
3847
48.2k
  }
3848
24.3k
3849
24.3k
  return map;
3850
24.3k
}
3851
3852
/* For each pair of basic maps in the map, check if the union of the two
3853
 * can be represented by a single basic map.
3854
 * If so, replace the pair by the single basic map and start over.
3855
 *
3856
 * We factor out any (hidden) common factor from the constraint
3857
 * coefficients to improve the detection of adjacent constraints.
3858
 *
3859
 * Since we are constructing the tableaus of the basic maps anyway,
3860
 * we exploit them to detect implicit equalities and redundant constraints.
3861
 * This also helps the coalescing as it can ignore the redundant constraints.
3862
 * In order to avoid confusion, we make all implicit equalities explicit
3863
 * in the basic maps.  We don't call isl_basic_map_gauss, though,
3864
 * as that may affect the number of constraints.
3865
 * This means that we have to call isl_basic_map_gauss at the end
3866
 * of the computation (in update_basic_maps) to ensure that
3867
 * the basic maps are not left in an unexpected state.
3868
 * For each basic map, we also compute the hash of the apparent affine hull
3869
 * for use in coalesce.
3870
 */
3871
__isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map)
3872
110k
{
3873
110k
  int i;
3874
110k
  unsigned n;
3875
110k
  isl_ctx *ctx;
3876
110k
  struct isl_coalesce_info *info = NULL;
3877
110k
3878
110k
  map = isl_map_remove_empty_parts(map);
3879
110k
  if (!map)
3880
0
    return NULL;
3881
110k
3882
110k
  if (map->n <= 1)
3883
85.9k
    return map;
3884
24.3k
3885
24.3k
  ctx = isl_map_get_ctx(map);
3886
24.3k
  map = isl_map_sort_divs(map);
3887
24.3k
  map = isl_map_cow(map);
3888
24.3k
3889
24.3k
  if (!map)
3890
0
    return NULL;
3891
24.3k
3892
24.3k
  n = map->n;
3893
24.3k
3894
24.3k
  info = isl_calloc_array(map->ctx, struct isl_coalesce_info, n);
3895
24.3k
  if (!info)
3896
0
    goto error;
3897
24.3k
3898
82.8k
  
for (i = 0; 24.3k
i < map->n;
++i58.4k
) {
3899
58.4k
    map->p[i] = isl_basic_map_reduce_coefficients(map->p[i]);
3900
58.4k
    if (!map->p[i])
3901
0
      goto error;
3902
58.4k
    info[i].bmap = isl_basic_map_copy(map->p[i]);
3903
58.4k
    info[i].tab = isl_tab_from_basic_map(info[i].bmap, 0);
3904
58.4k
    if (!info[i].tab)
3905
0
      goto error;
3906
58.4k
    if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT))
3907
58.4k
      
if (32.7k
isl_tab_detect_implicit_equalities(info[i].tab) < 032.7k
)
3908
0
        goto error;
3909
58.4k
    info[i].bmap = isl_tab_make_equalities_explicit(info[i].tab,
3910
58.4k
                info[i].bmap);
3911
58.4k
    if (!info[i].bmap)
3912
0
      goto error;
3913
58.4k
    if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT))
3914
58.4k
      
if (35.5k
isl_tab_detect_redundant(info[i].tab) < 035.5k
)
3915
0
        goto error;
3916
58.4k
    if (coalesce_info_set_hull_hash(&info[i]) < 0)
3917
0
      goto error;
3918
58.4k
  }
3919
82.8k
  
for (i = map->n - 1; 24.3k
i >= 0;
--i58.4k
)
3920
58.4k
    if (info[i].tab->empty)
3921
80
      drop(&info[i]);
3922
24.3k
3923
24.3k
  if (coalesce(ctx, n, info) < 0)
3924
0
    goto error;
3925
24.3k
3926
24.3k
  map = update_basic_maps(map, n, info);
3927
24.3k
3928
24.3k
  clear_coalesce_info(n, info);
3929
24.3k
3930
24.3k
  return map;
3931
0
error:
3932
0
  clear_coalesce_info(n, info);
3933
0
  isl_map_free(map);
3934
0
  return NULL;
3935
24.3k
}
3936
3937
/* For each pair of basic sets in the set, check if the union of the two
3938
 * can be represented by a single basic set.
3939
 * If so, replace the pair by the single basic set and start over.
3940
 */
3941
struct isl_set *isl_set_coalesce(struct isl_set *set)
3942
96.0k
{
3943
96.0k
  return set_from_map(isl_map_coalesce(set_to_map(set)));
3944
96.0k
}