Coverage Report

Created: 2018-04-24 22:41

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