Coverage Report

Created: 2018-06-19 22:08

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