Coverage Report

Created: 2019-04-25 15:07

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/Support/ISLTools.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------ ISLTools.cpp ----------------------------------------*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// Tools, utilities, helpers and extensions useful in conjunction with the
10
// Integer Set Library (isl).
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "polly/Support/ISLTools.h"
15
#include "llvm/Support/raw_ostream.h"
16
#include <cassert>
17
#include <vector>
18
19
using namespace polly;
20
21
namespace {
22
/// Create a map that shifts one dimension by an offset.
23
///
24
/// Example:
25
/// makeShiftDimAff({ [i0, i1] -> [o0, o1] }, 1, -2)
26
///   = { [i0, i1] -> [i0, i1 - 1] }
27
///
28
/// @param Space  The map space of the result. Must have equal number of in- and
29
///               out-dimensions.
30
/// @param Pos    Position to shift.
31
/// @param Amount Value added to the shifted dimension.
32
///
33
/// @return An isl_multi_aff for the map with this shifted dimension.
34
942
isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) {
35
942
  auto Identity = isl::multi_aff::identity(Space);
36
942
  if (Amount == 0)
37
0
    return Identity;
38
942
  auto ShiftAff = Identity.get_aff(Pos);
39
942
  ShiftAff = ShiftAff.set_constant_si(Amount);
40
942
  return Identity.set_aff(Pos, ShiftAff);
41
942
}
42
43
/// Construct a map that swaps two nested tuples.
44
///
45
/// @param FromSpace1 { Space1[] }
46
/// @param FromSpace2 { Space2[] }
47
///
48
/// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
49
isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1,
50
125
                                     isl::space FromSpace2) {
51
125
  // Fast-path on out-of-quota.
52
125
  if (!FromSpace1 || !FromSpace2)
53
0
    return {};
54
125
55
125
  assert(FromSpace1.is_set());
56
125
  assert(FromSpace2.is_set());
57
125
58
125
  unsigned Dims1 = FromSpace1.dim(isl::dim::set);
59
125
  unsigned Dims2 = FromSpace2.dim(isl::dim::set);
60
125
61
125
  isl::space FromSpace =
62
125
      FromSpace1.map_from_domain_and_range(FromSpace2).wrap();
63
125
  isl::space ToSpace = FromSpace2.map_from_domain_and_range(FromSpace1).wrap();
64
125
  isl::space MapSpace = FromSpace.map_from_domain_and_range(ToSpace);
65
125
66
125
  isl::basic_map Result = isl::basic_map::universe(MapSpace);
67
188
  for (auto i = Dims1 - Dims1; i < Dims1; 
i += 163
)
68
63
    Result = Result.equate(isl::dim::in, i, isl::dim::out, Dims2 + i);
69
336
  for (auto i = Dims2 - Dims2; i < Dims2; 
i += 1211
) {
70
211
    Result = Result.equate(isl::dim::in, Dims1 + i, isl::dim::out, i);
71
211
  }
72
125
73
125
  return Result;
74
125
}
75
76
/// Like makeTupleSwapBasicMap(isl::space,isl::space), but returns
77
/// an isl_map.
78
125
isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) {
79
125
  isl::basic_map BMapResult = makeTupleSwapBasicMap(FromSpace1, FromSpace2);
80
125
  return isl::map(BMapResult);
81
125
}
82
} // anonymous namespace
83
84
243
isl::map polly::beforeScatter(isl::map Map, bool Strict) {
85
243
  isl::space RangeSpace = Map.get_space().range();
86
243
  isl::map ScatterRel =
87
243
      Strict ? 
isl::map::lex_gt(RangeSpace)57
:
isl::map::lex_ge(RangeSpace)186
;
88
243
  return Map.apply_range(ScatterRel);
89
243
}
90
91
98
isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) {
92
98
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
93
98
94
109
  for (isl::map Map : UMap.get_map_list()) {
95
109
    isl::map After = beforeScatter(Map, Strict);
96
109
    Result = Result.add_map(After);
97
109
  }
98
98
99
98
  return Result;
100
98
}
101
102
149
isl::map polly::afterScatter(isl::map Map, bool Strict) {
103
149
  isl::space RangeSpace = Map.get_space().range();
104
149
  isl::map ScatterRel =
105
149
      Strict ? 
isl::map::lex_lt(RangeSpace)131
:
isl::map::lex_le(RangeSpace)18
;
106
149
  return Map.apply_range(ScatterRel);
107
149
}
108
109
98
isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) {
110
98
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
111
98
  for (isl::map Map : UMap.get_map_list()) {
112
54
    isl::map After = afterScatter(Map, Strict);
113
54
    Result = Result.add_map(After);
114
54
  }
115
98
  return Result;
116
98
}
117
118
isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,
119
93
                               bool InclTo) {
120
93
  isl::map AfterFrom = afterScatter(From, !InclFrom);
121
93
  isl::map BeforeTo = beforeScatter(To, !InclTo);
122
93
123
93
  return AfterFrom.intersect(BeforeTo);
124
93
}
125
126
isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To,
127
86
                                     bool InclFrom, bool InclTo) {
128
86
  isl::union_map AfterFrom = afterScatter(From, !InclFrom);
129
86
  isl::union_map BeforeTo = beforeScatter(To, !InclTo);
130
86
131
86
  return AfterFrom.intersect(BeforeTo);
132
86
}
133
134
289
isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) {
135
289
  if (!UMap)
136
0
    return nullptr;
137
289
138
289
  if (isl_union_map_n_map(UMap.get()) == 0)
139
3
    return isl::map::empty(ExpectedSpace);
140
286
141
286
  isl::map Result = isl::map::from_union_map(UMap);
142
286
  assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));
143
286
144
286
  return Result;
145
286
}
146
147
131
isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) {
148
131
  if (!USet)
149
0
    return nullptr;
150
131
151
131
  if (isl_union_set_n_set(USet.get()) == 0)
152
37
    return isl::set::empty(ExpectedSpace);
153
94
154
94
  isl::set Result(USet);
155
94
  assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));
156
94
157
94
  return Result;
158
94
}
159
160
583
unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {
161
583
  unsigned Dims = 0;
162
583
  for (isl::map Map : Schedule.get_map_list())
163
2.34k
    Dims = std::max(Dims, Map.dim(isl::dim::out));
164
583
  return Dims;
165
583
}
166
167
575
isl::space polly::getScatterSpace(const isl::union_map &Schedule) {
168
575
  if (!Schedule)
169
0
    return nullptr;
170
575
  unsigned Dims = getNumScatterDims(Schedule);
171
575
  isl::space ScatterSpace = Schedule.get_space().set_from_params();
172
575
  return ScatterSpace.add_dims(isl::dim::set, Dims);
173
575
}
174
175
isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
176
97
                                      bool RestrictDomain) {
177
97
  isl::union_map Result = isl::union_map::empty(USet.get_space());
178
114
  for (isl::set Set : USet.get_set_list()) {
179
114
    isl::map IdentityMap = isl::map::identity(Set.get_space().map_from_set());
180
114
    if (RestrictDomain)
181
57
      IdentityMap = IdentityMap.intersect_domain(Set);
182
114
    Result = Result.add_map(IdentityMap);
183
114
  }
184
97
  return Result;
185
97
}
186
187
125
isl::map polly::reverseDomain(isl::map Map) {
188
125
  isl::space DomSpace = Map.get_space().domain().unwrap();
189
125
  isl::space Space1 = DomSpace.domain();
190
125
  isl::space Space2 = DomSpace.range();
191
125
  isl::map Swap = makeTupleSwapMap(Space1, Space2);
192
125
  return Map.apply_domain(Swap);
193
125
}
194
195
165
isl::union_map polly::reverseDomain(const isl::union_map &UMap) {
196
165
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
197
165
  for (isl::map Map : UMap.get_map_list()) {
198
124
    auto Reversed = reverseDomain(std::move(Map));
199
124
    Result = Result.add_map(Reversed);
200
124
  }
201
165
  return Result;
202
165
}
203
204
566
isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {
205
566
  int NumDims = Set.dim(isl::dim::set);
206
566
  if (Pos < 0)
207
563
    Pos = NumDims + Pos;
208
566
  assert(Pos < NumDims && "Dimension index must be in range");
209
566
  isl::space Space = Set.get_space();
210
566
  Space = Space.map_from_domain_and_range(Space);
211
566
  isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);
212
566
  isl::map TranslatorMap = isl::map::from_multi_aff(Translator);
213
566
  return Set.apply(TranslatorMap);
214
566
}
215
216
550
isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
217
550
  isl::union_set Result = isl::union_set::empty(USet.get_space());
218
565
  for (isl::set Set : USet.get_set_list()) {
219
565
    isl::set Shifted = shiftDim(Set, Pos, Amount);
220
565
    Result = Result.add_set(Shifted);
221
565
  }
222
550
  return Result;
223
550
}
224
225
376
isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
226
376
  int NumDims = Map.dim(Dim);
227
376
  if (Pos < 0)
228
372
    Pos = NumDims + Pos;
229
376
  assert(Pos < NumDims && "Dimension index must be in range");
230
376
  isl::space Space = Map.get_space();
231
376
  switch (Dim) {
232
376
  case isl::dim::in:
233
371
    Space = Space.domain();
234
371
    break;
235
376
  case isl::dim::out:
236
5
    Space = Space.range();
237
5
    break;
238
376
  default:
239
0
    llvm_unreachable("Unsupported value for 'dim'");
240
376
  }
241
376
  Space = Space.map_from_domain_and_range(Space);
242
376
  isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);
243
376
  isl::map TranslatorMap = isl::map::from_multi_aff(Translator);
244
376
  switch (Dim) {
245
376
  case isl::dim::in:
246
371
    return Map.apply_domain(TranslatorMap);
247
376
  case isl::dim::out:
248
5
    return Map.apply_range(TranslatorMap);
249
376
  default:
250
0
    llvm_unreachable("Unsupported value for 'dim'");
251
376
  }
252
376
}
253
254
isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
255
538
                               int Amount) {
256
538
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
257
538
258
538
  for (isl::map Map : UMap.get_map_list()) {
259
374
    isl::map Shifted = shiftDim(Map, Dim, Pos, Amount);
260
374
    Result = Result.add_map(Shifted);
261
374
  }
262
538
  return Result;
263
538
}
264
265
604
void polly::simplify(isl::set &Set) {
266
604
  Set = isl::manage(isl_set_compute_divs(Set.copy()));
267
604
  Set = Set.detect_equalities();
268
604
  Set = Set.coalesce();
269
604
}
270
271
84
void polly::simplify(isl::union_set &USet) {
272
84
  USet = isl::manage(isl_union_set_compute_divs(USet.copy()));
273
84
  USet = USet.detect_equalities();
274
84
  USet = USet.coalesce();
275
84
}
276
277
719
void polly::simplify(isl::map &Map) {
278
719
  Map = isl::manage(isl_map_compute_divs(Map.copy()));
279
719
  Map = Map.detect_equalities();
280
719
  Map = Map.coalesce();
281
719
}
282
283
525
void polly::simplify(isl::union_map &UMap) {
284
525
  UMap = isl::manage(isl_union_map_compute_divs(UMap.copy()));
285
525
  UMap = UMap.detect_equalities();
286
525
  UMap = UMap.coalesce();
287
525
}
288
289
isl::union_map polly::computeReachingWrite(isl::union_map Schedule,
290
                                           isl::union_map Writes, bool Reverse,
291
375
                                           bool InclPrevDef, bool InclNextDef) {
292
375
293
375
  // { Scatter[] }
294
375
  isl::space ScatterSpace = getScatterSpace(Schedule);
295
375
296
375
  // { ScatterRead[] -> ScatterWrite[] }
297
375
  isl::map Relation;
298
375
  if (Reverse)
299
212
    Relation = InclPrevDef ? 
isl::map::lex_lt(ScatterSpace)25
300
212
                           : 
isl::map::lex_le(ScatterSpace)187
;
301
163
  else
302
163
    Relation = InclNextDef ? 
isl::map::lex_gt(ScatterSpace)157
303
163
                           : 
isl::map::lex_ge(ScatterSpace)6
;
304
375
305
375
  // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
306
375
  isl::map RelationMap = Relation.range_map().reverse();
307
375
308
375
  // { Element[] -> ScatterWrite[] }
309
375
  isl::union_map WriteAction = Schedule.apply_domain(Writes);
310
375
311
375
  // { ScatterWrite[] -> Element[] }
312
375
  isl::union_map WriteActionRev = WriteAction.reverse();
313
375
314
375
  // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
315
375
  isl::union_map DefSchedRelation =
316
375
      isl::union_map(RelationMap).apply_domain(WriteActionRev);
317
375
318
375
  // For each element, at every point in time, map to the times of previous
319
375
  // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
320
375
  isl::union_map ReachableWrites = DefSchedRelation.uncurry();
321
375
  if (Reverse)
322
212
    ReachableWrites = ReachableWrites.lexmin();
323
163
  else
324
163
    ReachableWrites = ReachableWrites.lexmax();
325
375
326
375
  // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
327
375
  isl::union_map SelfUse = WriteAction.range_map();
328
375
329
375
  if (InclPrevDef && 
InclNextDef29
) {
330
6
    // Add the Def itself to the solution.
331
6
    ReachableWrites = ReachableWrites.unite(SelfUse).coalesce();
332
369
  } else if (!InclPrevDef && 
!InclNextDef346
) {
333
10
    // Remove Def itself from the solution.
334
10
    ReachableWrites = ReachableWrites.subtract(SelfUse);
335
10
  }
336
375
337
375
  // { [Element[] -> ScatterRead[]] -> Domain[] }
338
375
  return ReachableWrites.apply_range(Schedule.reverse());
339
375
}
340
341
isl::union_map
342
polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,
343
                          isl::union_map Reads, bool ReadEltInSameInst,
344
82
                          bool IncludeLastRead, bool IncludeWrite) {
345
82
  // { Element[] -> Scatter[] }
346
82
  isl::union_map ReadActions = Schedule.apply_domain(Reads);
347
82
  isl::union_map WriteActions = Schedule.apply_domain(Writes);
348
82
349
82
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
350
82
  isl::union_map EltDomWrites =
351
82
      Writes.reverse().range_map().apply_range(Schedule);
352
82
353
82
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
354
82
  isl::union_map ReachingOverwrite = computeReachingWrite(
355
82
      Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);
356
82
357
82
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
358
82
  isl::union_map ReadsOverwritten =
359
82
      ReachingOverwrite.intersect_domain(ReadActions.wrap());
360
82
361
82
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
362
82
  isl::union_map ReadsOverwrittenRotated =
363
82
      reverseDomain(ReadsOverwritten).curry().reverse();
364
82
  isl::union_map LastOverwrittenRead = ReadsOverwrittenRotated.lexmax();
365
82
366
82
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
367
82
  isl::union_map BetweenLastReadOverwrite = betweenScatter(
368
82
      LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);
369
82
370
82
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
371
82
  isl::union_map ReachingOverwriteZone = computeReachingWrite(
372
82
      Schedule, Writes, true, IncludeLastRead, IncludeWrite);
373
82
374
82
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
375
82
  isl::union_map ReachingOverwriteRotated =
376
82
      reverseDomain(ReachingOverwriteZone).curry().reverse();
377
82
378
82
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
379
82
  isl::union_map WritesWithoutReads = ReachingOverwriteRotated.subtract_domain(
380
82
      ReadsOverwrittenRotated.domain());
381
82
382
82
  return BetweenLastReadOverwrite.unite(WritesWithoutReads)
383
82
      .domain_factor_domain();
384
82
}
385
386
isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
387
550
                                              bool InclStart, bool InclEnd) {
388
550
  if (!InclStart && 
InclEnd10
)
389
5
    return Zone;
390
545
391
545
  auto ShiftedZone = shiftDim(Zone, -1, -1);
392
545
  if (InclStart && 
!InclEnd540
)
393
535
    return ShiftedZone;
394
10
  else if (!InclStart && 
!InclEnd5
)
395
5
    return Zone.intersect(ShiftedZone);
396
5
397
5
  assert(InclStart && InclEnd);
398
5
  return Zone.unite(ShiftedZone);
399
5
}
400
401
isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
402
603
                                              bool InclStart, bool InclEnd) {
403
603
  if (!InclStart && 
InclEnd69
)
404
67
    return Zone;
405
536
406
536
  auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
407
536
  if (InclStart && 
!InclEnd534
)
408
532
    return ShiftedZone;
409
4
  else if (!InclStart && 
!InclEnd2
)
410
2
    return Zone.intersect(ShiftedZone);
411
2
412
2
  assert(InclStart && InclEnd);
413
2
  return Zone.unite(ShiftedZone);
414
2
}
415
416
isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim,
417
45
                                        bool InclStart, bool InclEnd) {
418
45
  if (!InclStart && InclEnd)
419
45
    return Zone;
420
0
421
0
  auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
422
0
  if (InclStart && !InclEnd)
423
0
    return ShiftedZone;
424
0
  else if (!InclStart && !InclEnd)
425
0
    return Zone.intersect(ShiftedZone);
426
0
427
0
  assert(InclStart && InclEnd);
428
0
  return Zone.unite(ShiftedZone);
429
0
}
430
431
211
isl::map polly::distributeDomain(isl::map Map) {
432
211
  // Note that we cannot take Map apart into { Domain[] -> Range1[] } and {
433
211
  // Domain[] -> Range2[] } and combine again. We would loose any relation
434
211
  // between Range1[] and Range2[] that is not also a constraint to Domain[].
435
211
436
211
  isl::space Space = Map.get_space();
437
211
  isl::space DomainSpace = Space.domain();
438
211
  unsigned DomainDims = DomainSpace.dim(isl::dim::set);
439
211
  isl::space RangeSpace = Space.range().unwrap();
440
211
  isl::space Range1Space = RangeSpace.domain();
441
211
  unsigned Range1Dims = Range1Space.dim(isl::dim::set);
442
211
  isl::space Range2Space = RangeSpace.range();
443
211
  unsigned Range2Dims = Range2Space.dim(isl::dim::set);
444
211
445
211
  isl::space OutputSpace =
446
211
      DomainSpace.map_from_domain_and_range(Range1Space)
447
211
          .wrap()
448
211
          .map_from_domain_and_range(
449
211
              DomainSpace.map_from_domain_and_range(Range2Space).wrap());
450
211
451
211
  isl::basic_map Translator = isl::basic_map::universe(
452
211
      Space.wrap().map_from_domain_and_range(OutputSpace.wrap()));
453
211
454
425
  for (unsigned i = 0; i < DomainDims; 
i += 1214
) {
455
214
    Translator = Translator.equate(isl::dim::in, i, isl::dim::out, i);
456
214
    Translator = Translator.equate(isl::dim::in, i, isl::dim::out,
457
214
                                   DomainDims + Range1Dims + i);
458
214
  }
459
687
  for (unsigned i = 0; i < Range1Dims; 
i += 1476
)
460
476
    Translator = Translator.equate(isl::dim::in, DomainDims + i, isl::dim::out,
461
476
                                   DomainDims + i);
462
378
  for (unsigned i = 0; i < Range2Dims; 
i += 1167
)
463
167
    Translator = Translator.equate(isl::dim::in, DomainDims + Range1Dims + i,
464
167
                                   isl::dim::out,
465
167
                                   DomainDims + Range1Dims + DomainDims + i);
466
211
467
211
  return Map.wrap().apply(Translator).unwrap();
468
211
}
469
470
120
isl::union_map polly::distributeDomain(isl::union_map UMap) {
471
120
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
472
209
  for (isl::map Map : UMap.get_map_list()) {
473
209
    auto Distributed = distributeDomain(Map);
474
209
    Result = Result.add_map(Distributed);
475
209
  }
476
120
  return Result;
477
120
}
478
479
57
isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {
480
57
481
57
  // { Factor[] -> Factor[] }
482
57
  isl::union_map Factors = makeIdentityMap(Factor, true);
483
57
484
57
  return Factors.product(UMap);
485
57
}
486
487
isl::union_map polly::applyDomainRange(isl::union_map UMap,
488
54
                                       isl::union_map Func) {
489
54
  // This implementation creates unnecessary cross products of the
490
54
  // DomainDomain[] and Func. An alternative implementation could reverse
491
54
  // domain+uncurry,apply Func to what now is the domain, then undo the
492
54
  // preparing transformation. Another alternative implementation could create a
493
54
  // translator map for each piece.
494
54
495
54
  // { DomainDomain[] }
496
54
  isl::union_set DomainDomain = UMap.domain().unwrap().domain();
497
54
498
54
  // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]]
499
54
  // }
500
54
  isl::union_map LifetedFunc = liftDomains(std::move(Func), DomainDomain);
501
54
502
54
  return UMap.apply_domain(LifetedFunc);
503
54
}
504
505
184
isl::map polly::intersectRange(isl::map Map, isl::union_set Range) {
506
184
  isl::set RangeSet = Range.extract_set(Map.get_space().range());
507
184
  return Map.intersect_range(RangeSet);
508
184
}
509
510
158
isl::val polly::getConstant(isl::pw_aff PwAff, bool Max, bool Min) {
511
158
  assert(!Max || !Min); // Cannot return min and max at the same time.
512
158
  isl::val Result;
513
158
  isl::stat Stat = PwAff.foreach_piece(
514
158
      [=, &Result](isl::set Set, isl::aff Aff) -> isl::stat {
515
158
        if (Result && 
Result.is_nan()0
)
516
0
          return isl::stat::ok();
517
158
518
158
        // TODO: If Min/Max, we can also determine a minimum/maximum value if
519
158
        // Set is constant-bounded.
520
158
        if (!Aff.is_cst()) {
521
0
          Result = isl::val::nan(Aff.get_ctx());
522
0
          return isl::stat::error();
523
0
        }
524
158
525
158
        isl::val ThisVal = Aff.get_constant_val();
526
158
        if (!Result) {
527
158
          Result = ThisVal;
528
158
          return isl::stat::ok();
529
158
        }
530
0
531
0
        if (Result.eq(ThisVal))
532
0
          return isl::stat::ok();
533
0
534
0
        if (Max && ThisVal.gt(Result)) {
535
0
          Result = ThisVal;
536
0
          return isl::stat::ok();
537
0
        }
538
0
539
0
        if (Min && ThisVal.lt(Result)) {
540
0
          Result = ThisVal;
541
0
          return isl::stat::ok();
542
0
        }
543
0
544
0
        // Not compatible
545
0
        Result = isl::val::nan(Aff.get_ctx());
546
0
        return isl::stat::error();
547
0
      });
548
158
549
158
  if (Stat.is_error())
550
0
    return {};
551
158
552
158
  return Result;
553
158
}
554
555
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
556
static void foreachPoint(const isl::set &Set,
557
                         const std::function<void(isl::point P)> &F) {
558
  Set.foreach_point([&](isl::point P) -> isl::stat {
559
    F(P);
560
    return isl::stat::ok();
561
  });
562
}
563
564
static void foreachPoint(isl::basic_set BSet,
565
                         const std::function<void(isl::point P)> &F) {
566
  foreachPoint(isl::set(BSet), F);
567
}
568
569
/// Determine the sorting order of the sets @p A and @p B without considering
570
/// the space structure.
571
///
572
/// Ordering is based on the lower bounds of the set's dimensions. First
573
/// dimensions are considered first.
574
static int flatCompare(const isl::basic_set &A, const isl::basic_set &B) {
575
  unsigned ALen = A.dim(isl::dim::set);
576
  unsigned BLen = B.dim(isl::dim::set);
577
  unsigned Len = std::min(ALen, BLen);
578
579
  for (unsigned i = 0; i < Len; i += 1) {
580
    isl::basic_set ADim =
581
        A.project_out(isl::dim::param, 0, A.dim(isl::dim::param))
582
            .project_out(isl::dim::set, i + 1, ALen - i - 1)
583
            .project_out(isl::dim::set, 0, i);
584
    isl::basic_set BDim =
585
        B.project_out(isl::dim::param, 0, B.dim(isl::dim::param))
586
            .project_out(isl::dim::set, i + 1, BLen - i - 1)
587
            .project_out(isl::dim::set, 0, i);
588
589
    isl::basic_set AHull = isl::set(ADim).convex_hull();
590
    isl::basic_set BHull = isl::set(BDim).convex_hull();
591
592
    bool ALowerBounded =
593
        bool(isl::set(AHull).dim_has_any_lower_bound(isl::dim::set, 0));
594
    bool BLowerBounded =
595
        bool(isl::set(BHull).dim_has_any_lower_bound(isl::dim::set, 0));
596
597
    int BoundedCompare = BLowerBounded - ALowerBounded;
598
    if (BoundedCompare != 0)
599
      return BoundedCompare;
600
601
    if (!ALowerBounded || !BLowerBounded)
602
      continue;
603
604
    isl::pw_aff AMin = isl::set(ADim).dim_min(0);
605
    isl::pw_aff BMin = isl::set(BDim).dim_min(0);
606
607
    isl::val AMinVal = polly::getConstant(AMin, false, true);
608
    isl::val BMinVal = polly::getConstant(BMin, false, true);
609
610
    int MinCompare = AMinVal.sub(BMinVal).sgn();
611
    if (MinCompare != 0)
612
      return MinCompare;
613
  }
614
615
  // If all the dimensions' lower bounds are equal or incomparable, sort based
616
  // on the number of dimensions.
617
  return ALen - BLen;
618
}
619
620
/// Compare the sets @p A and @p B according to their nested space structure.
621
/// Returns 0 if the structure is considered equal.
622
/// If @p ConsiderTupleLen is false, the number of dimensions in a tuple are
623
/// ignored, i.e. a tuple with the same name but different number of dimensions
624
/// are considered equal.
625
static int structureCompare(const isl::space &ASpace, const isl::space &BSpace,
626
                            bool ConsiderTupleLen) {
627
  int WrappingCompare = bool(ASpace.is_wrapping()) - bool(BSpace.is_wrapping());
628
  if (WrappingCompare != 0)
629
    return WrappingCompare;
630
631
  if (ASpace.is_wrapping() && BSpace.is_wrapping()) {
632
    isl::space AMap = ASpace.unwrap();
633
    isl::space BMap = BSpace.unwrap();
634
635
    int FirstResult =
636
        structureCompare(AMap.domain(), BMap.domain(), ConsiderTupleLen);
637
    if (FirstResult != 0)
638
      return FirstResult;
639
640
    return structureCompare(AMap.range(), BMap.range(), ConsiderTupleLen);
641
  }
642
643
  std::string AName;
644
  if (ASpace.has_tuple_name(isl::dim::set))
645
    AName = ASpace.get_tuple_name(isl::dim::set);
646
647
  std::string BName;
648
  if (BSpace.has_tuple_name(isl::dim::set))
649
    BName = BSpace.get_tuple_name(isl::dim::set);
650
651
  int NameCompare = AName.compare(BName);
652
  if (NameCompare != 0)
653
    return NameCompare;
654
655
  if (ConsiderTupleLen) {
656
    int LenCompare = BSpace.dim(isl::dim::set) - ASpace.dim(isl::dim::set);
657
    if (LenCompare != 0)
658
      return LenCompare;
659
  }
660
661
  return 0;
662
}
663
664
/// Compare the sets @p A and @p B according to their nested space structure. If
665
/// the structure is the same, sort using the dimension lower bounds.
666
/// Returns an std::sort compatible bool.
667
static bool orderComparer(const isl::basic_set &A, const isl::basic_set &B) {
668
  isl::space ASpace = A.get_space();
669
  isl::space BSpace = B.get_space();
670
671
  // Ignoring number of dimensions first ensures that structures with same tuple
672
  // names, but different number of dimensions are still sorted close together.
673
  int TupleNestingCompare = structureCompare(ASpace, BSpace, false);
674
  if (TupleNestingCompare != 0)
675
    return TupleNestingCompare < 0;
676
677
  int TupleCompare = structureCompare(ASpace, BSpace, true);
678
  if (TupleCompare != 0)
679
    return TupleCompare < 0;
680
681
  return flatCompare(A, B) < 0;
682
}
683
684
/// Print a string representation of @p USet to @p OS.
685
///
686
/// The pieces of @p USet are printed in a sorted order. Spaces with equal or
687
/// similar nesting structure are printed together. Compared to isl's own
688
/// printing function the uses the structure itself as base of the sorting, not
689
/// a hash of it. It ensures that e.g. maps spaces with same domain structure
690
/// are printed together. Set pieces with same structure are printed in order of
691
/// their lower bounds.
692
///
693
/// @param USet     Polyhedra to print.
694
/// @param OS       Target stream.
695
/// @param Simplify Whether to simplify the polyhedron before printing.
696
/// @param IsMap    Whether @p USet is a wrapped map. If true, sets are
697
///                 unwrapped before printing to again appear as a map.
698
static void printSortedPolyhedra(isl::union_set USet, llvm::raw_ostream &OS,
699
                                 bool Simplify, bool IsMap) {
700
  if (!USet) {
701
    OS << "<null>\n";
702
    return;
703
  }
704
705
  if (Simplify)
706
    simplify(USet);
707
708
  // Get all the polyhedra.
709
  std::vector<isl::basic_set> BSets;
710
711
  for (isl::set Set : USet.get_set_list()) {
712
    for (isl::basic_set BSet : Set.get_basic_set_list()) {
713
      BSets.push_back(BSet);
714
    }
715
  }
716
717
  if (BSets.empty()) {
718
    OS << "{\n}\n";
719
    return;
720
  }
721
722
  // Sort the polyhedra.
723
  llvm::sort(BSets, orderComparer);
724
725
  // Print the polyhedra.
726
  bool First = true;
727
  for (const isl::basic_set &BSet : BSets) {
728
    std::string Str;
729
    if (IsMap)
730
      Str = isl::map(BSet.unwrap()).to_str();
731
    else
732
      Str = isl::set(BSet).to_str();
733
    size_t OpenPos = Str.find_first_of('{');
734
    assert(OpenPos != std::string::npos);
735
    size_t ClosePos = Str.find_last_of('}');
736
    assert(ClosePos != std::string::npos);
737
738
    if (First)
739
      OS << llvm::StringRef(Str).substr(0, OpenPos + 1) << "\n ";
740
    else
741
      OS << ";\n ";
742
743
    OS << llvm::StringRef(Str).substr(OpenPos + 1, ClosePos - OpenPos - 2);
744
    First = false;
745
  }
746
  assert(!First);
747
  OS << "\n}\n";
748
}
749
750
static void recursiveExpand(isl::basic_set BSet, int Dim, isl::set &Expanded) {
751
  int Dims = BSet.dim(isl::dim::set);
752
  if (Dim >= Dims) {
753
    Expanded = Expanded.unite(BSet);
754
    return;
755
  }
756
757
  isl::basic_set DimOnly =
758
      BSet.project_out(isl::dim::param, 0, BSet.dim(isl::dim::param))
759
          .project_out(isl::dim::set, Dim + 1, Dims - Dim - 1)
760
          .project_out(isl::dim::set, 0, Dim);
761
  if (!DimOnly.is_bounded()) {
762
    recursiveExpand(BSet, Dim + 1, Expanded);
763
    return;
764
  }
765
766
  foreachPoint(DimOnly, [&, Dim](isl::point P) {
767
    isl::val Val = P.get_coordinate_val(isl::dim::set, 0);
768
    isl::basic_set FixBSet = BSet.fix_val(isl::dim::set, Dim, Val);
769
    recursiveExpand(FixBSet, Dim + 1, Expanded);
770
  });
771
}
772
773
/// Make each point of a set explicit.
774
///
775
/// "Expanding" makes each point a set contains explicit. That is, the result is
776
/// a set of singleton polyhedra. Unbounded dimensions are not expanded.
777
///
778
/// Example:
779
///   { [i] : 0 <= i < 2 }
780
/// is expanded to:
781
///   { [0]; [1] }
782
static isl::set expand(const isl::set &Set) {
783
  isl::set Expanded = isl::set::empty(Set.get_space());
784
  for (isl::basic_set BSet : Set.get_basic_set_list())
785
    recursiveExpand(BSet, 0, Expanded);
786
  return Expanded;
787
}
788
789
/// Expand all points of a union set explicit.
790
///
791
/// @see expand(const isl::set)
792
static isl::union_set expand(const isl::union_set &USet) {
793
  isl::union_set Expanded = isl::union_set::empty(USet.get_space());
794
  for (isl::set Set : USet.get_set_list()) {
795
    isl::set SetExpanded = expand(Set);
796
    Expanded = Expanded.add_set(SetExpanded);
797
  }
798
  return Expanded;
799
}
800
801
LLVM_DUMP_METHOD void polly::dumpPw(const isl::set &Set) {
802
  printSortedPolyhedra(Set, llvm::errs(), true, false);
803
}
804
805
LLVM_DUMP_METHOD void polly::dumpPw(const isl::map &Map) {
806
  printSortedPolyhedra(Map.wrap(), llvm::errs(), true, true);
807
}
808
809
LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_set &USet) {
810
  printSortedPolyhedra(USet, llvm::errs(), true, false);
811
}
812
813
LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_map &UMap) {
814
  printSortedPolyhedra(UMap.wrap(), llvm::errs(), true, true);
815
}
816
817
LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_set *Set) {
818
  dumpPw(isl::manage_copy(Set));
819
}
820
821
LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_map *Map) {
822
  dumpPw(isl::manage_copy(Map));
823
}
824
825
LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_set *USet) {
826
  dumpPw(isl::manage_copy(USet));
827
}
828
829
LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_map *UMap) {
830
  dumpPw(isl::manage_copy(UMap));
831
}
832
833
LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::set &Set) {
834
  printSortedPolyhedra(expand(Set), llvm::errs(), false, false);
835
}
836
837
LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::map &Map) {
838
  printSortedPolyhedra(expand(Map.wrap()), llvm::errs(), false, true);
839
}
840
841
LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_set &USet) {
842
  printSortedPolyhedra(expand(USet), llvm::errs(), false, false);
843
}
844
845
LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_map &UMap) {
846
  printSortedPolyhedra(expand(UMap.wrap()), llvm::errs(), false, true);
847
}
848
849
LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_set *Set) {
850
  dumpExpanded(isl::manage_copy(Set));
851
}
852
853
LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_map *Map) {
854
  dumpExpanded(isl::manage_copy(Map));
855
}
856
857
LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_set *USet) {
858
  dumpExpanded(isl::manage_copy(USet));
859
}
860
861
LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_map *UMap) {
862
  dumpExpanded(isl::manage_copy(UMap));
863
}
864
#endif