Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
17
using namespace polly;
18
19
namespace {
20
/// Create a map that shifts one dimension by an offset.
21
///
22
/// Example:
23
/// makeShiftDimAff({ [i0, i1] -> [o0, o1] }, 1, -2)
24
///   = { [i0, i1] -> [i0, i1 - 1] }
25
///
26
/// @param Space  The map space of the result. Must have equal number of in- and
27
///               out-dimensions.
28
/// @param Pos    Position to shift.
29
/// @param Amount Value added to the shifted dimension.
30
///
31
/// @return An isl_multi_aff for the map with this shifted dimension.
32
784
isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) {
33
784
  auto Identity = give(isl_multi_aff_identity(Space.take()));
34
784
  if (Amount == 0)
35
0
    return Identity;
36
784
  auto ShiftAff = give(isl_multi_aff_get_aff(Identity.keep(), Pos));
37
784
  ShiftAff = give(isl_aff_set_constant_si(ShiftAff.take(), Amount));
38
784
  return give(isl_multi_aff_set_aff(Identity.take(), Pos, ShiftAff.take()));
39
784
}
40
41
/// Construct a map that swaps two nested tuples.
42
///
43
/// @param FromSpace1 { Space1[] }
44
/// @param FromSpace2 { Space2[] }
45
///
46
/// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
47
isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1,
48
104
                                     isl::space FromSpace2) {
49
104
  assert(isl_space_is_set(FromSpace1.keep()) != isl_bool_false);
50
104
  assert(isl_space_is_set(FromSpace2.keep()) != isl_bool_false);
51
104
52
104
  auto Dims1 = isl_space_dim(FromSpace1.keep(), isl_dim_set);
53
104
  auto Dims2 = isl_space_dim(FromSpace2.keep(), isl_dim_set);
54
104
  auto FromSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
55
104
      FromSpace1.copy(), FromSpace2.copy())));
56
104
  auto ToSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
57
104
      FromSpace2.take(), FromSpace1.take())));
58
104
  auto MapSpace = give(
59
104
      isl_space_map_from_domain_and_range(FromSpace.take(), ToSpace.take()));
60
104
61
104
  auto Result = give(isl_basic_map_universe(MapSpace.take()));
62
146
  for (auto i = Dims1 - Dims1; 
i < Dims1146
;
i += 142
) {
63
42
    Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, i,
64
42
                                       isl_dim_out, Dims2 + i));
65
42
  }
66
250
  for (auto i = Dims2 - Dims2; 
i < Dims2250
;
i += 1146
) {
67
146
    Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, Dims1 + i,
68
146
                                       isl_dim_out, i));
69
146
  }
70
104
71
104
  return Result;
72
104
}
73
74
/// Like makeTupleSwapBasicMap(isl::space,isl::space), but returns
75
/// an isl_map.
76
104
isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) {
77
104
  auto BMapResult =
78
104
      makeTupleSwapBasicMap(std::move(FromSpace1), std::move(FromSpace2));
79
104
  return give(isl_map_from_basic_map(BMapResult.take()));
80
104
}
81
} // anonymous namespace
82
83
184
isl::map polly::beforeScatter(isl::map Map, bool Strict) {
84
184
  auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
85
42
  auto ScatterRel = give(Strict ? isl_map_lex_gt(RangeSpace.take())
86
142
                                : isl_map_lex_ge(RangeSpace.take()));
87
184
  return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
88
184
}
89
90
83
isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) {
91
83
  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
92
94
  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
93
94
    auto After = beforeScatter(Map, Strict);
94
94
    Result = give(isl_union_map_add_map(Result.take(), After.take()));
95
94
    return isl::stat::ok;
96
94
  });
97
83
  return Result;
98
83
}
99
100
114
isl::map polly::afterScatter(isl::map Map, bool Strict) {
101
114
  auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
102
96
  auto ScatterRel = give(Strict ? isl_map_lex_lt(RangeSpace.take())
103
18
                                : isl_map_lex_le(RangeSpace.take()));
104
114
  return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
105
114
}
106
107
83
isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) {
108
83
  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
109
48
  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
110
48
    auto After = afterScatter(Map, Strict);
111
48
    Result = give(isl_union_map_add_map(Result.take(), After.take()));
112
48
    return isl::stat::ok;
113
48
  });
114
83
  return Result;
115
83
}
116
117
isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,
118
64
                               bool InclTo) {
119
64
  auto AfterFrom = afterScatter(From, !InclFrom);
120
64
  auto BeforeTo = beforeScatter(To, !InclTo);
121
64
122
64
  return give(isl_map_intersect(AfterFrom.take(), BeforeTo.take()));
123
64
}
124
125
isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To,
126
71
                                     bool InclFrom, bool InclTo) {
127
71
  auto AfterFrom = afterScatter(From, !InclFrom);
128
71
  auto BeforeTo = beforeScatter(To, !InclTo);
129
71
130
71
  return give(isl_union_map_intersect(AfterFrom.take(), BeforeTo.take()));
131
71
}
132
133
311
isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) {
134
311
  if (!UMap)
135
0
    return nullptr;
136
311
137
311
  
if (311
isl_union_map_n_map(UMap.keep()) == 0311
)
138
3
    return isl::map::empty(ExpectedSpace);
139
308
140
308
  isl::map Result = isl::map::from_union_map(UMap);
141
308
  assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));
142
308
143
308
  return Result;
144
308
}
145
146
28
isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) {
147
28
  if (!USet)
148
0
    return nullptr;
149
28
150
28
  
if (28
isl_union_set_n_set(USet.keep()) == 028
)
151
1
    return isl::set::empty(ExpectedSpace);
152
27
153
27
  isl::set Result(USet);
154
27
  assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));
155
27
156
27
  return Result;
157
27
}
158
159
497
unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {
160
497
  unsigned Dims = 0;
161
1.81k
  Schedule.foreach_map([&Dims](isl::map Map) -> isl::stat {
162
1.81k
    Dims = std::max(Dims, isl_map_dim(Map.keep(), isl_dim_out));
163
1.81k
    return isl::stat::ok;
164
1.81k
  });
165
497
  return Dims;
166
497
}
167
168
489
isl::space polly::getScatterSpace(const isl::union_map &Schedule) {
169
489
  if (!Schedule)
170
0
    return nullptr;
171
489
  auto Dims = getNumScatterDims(Schedule);
172
489
  auto ScatterSpace =
173
489
      give(isl_space_set_from_params(isl_union_map_get_space(Schedule.keep())));
174
489
  return give(isl_space_add_dims(ScatterSpace.take(), isl_dim_set, Dims));
175
489
}
176
177
isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
178
76
                                      bool RestrictDomain) {
179
76
  auto Result = give(isl_union_map_empty(isl_union_set_get_space(USet.keep())));
180
81
  USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
181
81
    auto IdentityMap = give(isl_map_identity(
182
81
        isl_space_map_from_set(isl_set_get_space(Set.keep()))));
183
81
    if (RestrictDomain)
184
45
      IdentityMap =
185
45
          give(isl_map_intersect_domain(IdentityMap.take(), Set.take()));
186
81
    Result = give(isl_union_map_add_map(Result.take(), IdentityMap.take()));
187
81
    return isl::stat::ok;
188
81
  });
189
76
  return Result;
190
76
}
191
192
104
isl::map polly::reverseDomain(isl::map Map) {
193
104
  auto DomSpace =
194
104
      give(isl_space_unwrap(isl_space_domain(isl_map_get_space(Map.keep()))));
195
104
  auto Space1 = give(isl_space_domain(DomSpace.copy()));
196
104
  auto Space2 = give(isl_space_range(DomSpace.take()));
197
104
  auto Swap = makeTupleSwapMap(std::move(Space1), std::move(Space2));
198
104
  return give(isl_map_apply_domain(Map.take(), Swap.take()));
199
104
}
200
201
135
isl::union_map polly::reverseDomain(const isl::union_map &UMap) {
202
135
  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
203
103
  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
204
103
    auto Reversed = reverseDomain(std::move(Map));
205
103
    Result = give(isl_union_map_add_map(Result.take(), Reversed.take()));
206
103
    return isl::stat::ok;
207
103
  });
208
135
  return Result;
209
135
}
210
211
506
isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {
212
506
  int NumDims = isl_set_dim(Set.keep(), isl_dim_set);
213
506
  if (Pos < 0)
214
503
    Pos = NumDims + Pos;
215
506
  assert(Pos < NumDims && "Dimension index must be in range");
216
506
  auto Space = give(isl_set_get_space(Set.keep()));
217
506
  Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
218
506
  auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
219
506
  auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
220
506
  return give(isl_set_apply(Set.take(), TranslatorMap.take()));
221
506
}
222
223
490
isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
224
490
  auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
225
505
  USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
226
505
    auto Shifted = shiftDim(Set, Pos, Amount);
227
505
    Result = give(isl_union_set_add_set(Result.take(), Shifted.take()));
228
505
    return isl::stat::ok;
229
505
  });
230
490
  return Result;
231
490
}
232
233
278
isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
234
278
  int NumDims = Map.dim(Dim);
235
278
  if (Pos < 0)
236
274
    Pos = NumDims + Pos;
237
278
  assert(Pos < NumDims && "Dimension index must be in range");
238
278
  auto Space = give(isl_map_get_space(Map.keep()));
239
278
  switch (Dim) {
240
273
  case isl::dim::in:
241
273
    Space = std::move(Space).domain();
242
273
    break;
243
5
  case isl::dim::out:
244
5
    Space = give(isl_space_range(Space.take()));
245
5
    break;
246
0
  default:
247
0
    llvm_unreachable("Unsupported value for 'dim'");
248
278
  }
249
278
  Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
250
278
  auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
251
278
  auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
252
278
  switch (Dim) {
253
273
  case isl::dim::in:
254
273
    return Map.apply_domain(TranslatorMap);
255
5
  case isl::dim::out:
256
5
    return Map.apply_range(TranslatorMap);
257
0
  default:
258
0
    llvm_unreachable("Unsupported value for 'dim'");
259
0
  }
260
0
}
261
262
isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
263
478
                               int Amount) {
264
478
  auto Result = isl::union_map::empty(UMap.get_space());
265
478
266
276
  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
267
276
    auto Shifted = shiftDim(Map, Dim, Pos, Amount);
268
276
    Result = std::move(Result).add_map(Shifted);
269
276
    return isl::stat::ok;
270
276
  });
271
478
  return Result;
272
478
}
273
274
37
void polly::simplify(isl::set &Set) {
275
37
  Set = give(isl_set_compute_divs(Set.take()));
276
37
  Set = give(isl_set_detect_equalities(Set.take()));
277
37
  Set = give(isl_set_coalesce(Set.take()));
278
37
}
279
280
59
void polly::simplify(isl::union_set &USet) {
281
59
  USet = give(isl_union_set_compute_divs(USet.take()));
282
59
  USet = give(isl_union_set_detect_equalities(USet.take()));
283
59
  USet = give(isl_union_set_coalesce(USet.take()));
284
59
}
285
286
501
void polly::simplify(isl::map &Map) {
287
501
  Map = give(isl_map_compute_divs(Map.take()));
288
501
  Map = give(isl_map_detect_equalities(Map.take()));
289
501
  Map = give(isl_map_coalesce(Map.take()));
290
501
}
291
292
354
void polly::simplify(isl::union_map &UMap) {
293
354
  UMap = give(isl_union_map_compute_divs(UMap.take()));
294
354
  UMap = give(isl_union_map_detect_equalities(UMap.take()));
295
354
  UMap = give(isl_union_map_coalesce(UMap.take()));
296
354
}
297
298
isl::union_map polly::computeReachingWrite(isl::union_map Schedule,
299
                                           isl::union_map Writes, bool Reverse,
300
317
                                           bool InclPrevDef, bool InclNextDef) {
301
317
302
317
  // { Scatter[] }
303
317
  auto ScatterSpace = getScatterSpace(Schedule);
304
317
305
317
  // { ScatterRead[] -> ScatterWrite[] }
306
317
  isl::map Relation;
307
317
  if (Reverse)
308
172
    
Relation = give(InclPrevDef ? 172
isl_map_lex_lt(ScatterSpace.take())25
309
172
                                : isl_map_lex_le(ScatterSpace.take()));
310
317
  else
311
145
    
Relation = give(InclNextDef ? 145
isl_map_lex_gt(ScatterSpace.take())139
312
145
                                : isl_map_lex_ge(ScatterSpace.take()));
313
317
314
317
  // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
315
317
  auto RelationMap = give(isl_map_reverse(isl_map_range_map(Relation.take())));
316
317
317
317
  // { Element[] -> ScatterWrite[] }
318
317
  auto WriteAction =
319
317
      give(isl_union_map_apply_domain(Schedule.copy(), Writes.take()));
320
317
321
317
  // { ScatterWrite[] -> Element[] }
322
317
  auto WriteActionRev = give(isl_union_map_reverse(WriteAction.copy()));
323
317
324
317
  // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
325
317
  auto DefSchedRelation = give(isl_union_map_apply_domain(
326
317
      isl_union_map_from_map(RelationMap.take()), WriteActionRev.take()));
327
317
328
317
  // For each element, at every point in time, map to the times of previous
329
317
  // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
330
317
  auto ReachableWrites = give(isl_union_map_uncurry(DefSchedRelation.take()));
331
317
  if (Reverse)
332
172
    ReachableWrites = give(isl_union_map_lexmin(ReachableWrites.copy()));
333
317
  else
334
145
    ReachableWrites = give(isl_union_map_lexmax(ReachableWrites.copy()));
335
317
336
317
  // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
337
317
  auto SelfUse = give(isl_union_map_range_map(WriteAction.take()));
338
317
339
317
  if (
InclPrevDef && 317
InclNextDef29
) {
340
6
    // Add the Def itself to the solution.
341
6
    ReachableWrites =
342
6
        give(isl_union_map_union(ReachableWrites.take(), SelfUse.take()));
343
6
    ReachableWrites = give(isl_union_map_coalesce(ReachableWrites.take()));
344
317
  } else 
if (311
!InclPrevDef && 311
!InclNextDef288
) {
345
10
    // Remove Def itself from the solution.
346
10
    ReachableWrites =
347
10
        give(isl_union_map_subtract(ReachableWrites.take(), SelfUse.take()));
348
10
  }
349
317
350
317
  // { [Element[] -> ScatterRead[]] -> Domain[] }
351
317
  auto ReachableWriteDomain = give(isl_union_map_apply_range(
352
317
      ReachableWrites.take(), isl_union_map_reverse(Schedule.take())));
353
317
354
317
  return ReachableWriteDomain;
355
317
}
356
357
isl::union_map
358
polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,
359
                          isl::union_map Reads, bool ReadEltInSameInst,
360
67
                          bool IncludeLastRead, bool IncludeWrite) {
361
67
  // { Element[] -> Scatter[] }
362
67
  auto ReadActions =
363
67
      give(isl_union_map_apply_domain(Schedule.copy(), Reads.take()));
364
67
  auto WriteActions =
365
67
      give(isl_union_map_apply_domain(Schedule.copy(), Writes.copy()));
366
67
367
67
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
368
67
  auto EltDomWrites = give(isl_union_map_apply_range(
369
67
      isl_union_map_range_map(isl_union_map_reverse(Writes.copy())),
370
67
      Schedule.copy()));
371
67
372
67
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
373
67
  auto ReachingOverwrite = computeReachingWrite(
374
67
      Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);
375
67
376
67
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
377
67
  auto ReadsOverwritten = give(isl_union_map_intersect_domain(
378
67
      ReachingOverwrite.take(), isl_union_map_wrap(ReadActions.take())));
379
67
380
67
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
381
67
  auto ReadsOverwrittenRotated = give(isl_union_map_reverse(
382
67
      isl_union_map_curry(reverseDomain(ReadsOverwritten).take())));
383
67
  auto LastOverwrittenRead =
384
67
      give(isl_union_map_lexmax(ReadsOverwrittenRotated.copy()));
385
67
386
67
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
387
67
  auto BetweenLastReadOverwrite = betweenScatter(
388
67
      LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);
389
67
390
67
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
391
67
  isl::union_map ReachingOverwriteZone = computeReachingWrite(
392
67
      Schedule, Writes, true, IncludeLastRead, IncludeWrite);
393
67
394
67
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
395
67
  isl::union_map ReachingOverwriteRotated =
396
67
      reverseDomain(ReachingOverwriteZone).curry().reverse();
397
67
398
67
  // { [Element[] -> DomainWrite[]] -> Scatter[] }
399
67
  isl::union_map WritesWithoutReads = ReachingOverwriteRotated.subtract_domain(
400
67
      ReadsOverwrittenRotated.domain());
401
67
402
67
  return BetweenLastReadOverwrite.unite(WritesWithoutReads)
403
67
      .domain_factor_domain();
404
67
}
405
406
isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
407
490
                                              bool InclStart, bool InclEnd) {
408
490
  if (
!InclStart && 490
InclEnd10
)
409
5
    return Zone;
410
485
411
485
  auto ShiftedZone = shiftDim(Zone, -1, -1);
412
485
  if (
InclStart && 485
!InclEnd480
)
413
475
    return ShiftedZone;
414
10
  else 
if (10
!InclStart && 10
!InclEnd5
)
415
5
    return give(isl_union_set_intersect(Zone.take(), ShiftedZone.take()));
416
5
417
485
  assert(InclStart && InclEnd);
418
5
  return give(isl_union_set_union(Zone.take(), ShiftedZone.take()));
419
5
}
420
421
isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
422
511
                                              bool InclStart, bool InclEnd) {
423
511
  if (
!InclStart && 511
InclEnd37
)
424
35
    return Zone;
425
476
426
476
  auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
427
476
  if (
InclStart && 476
!InclEnd474
)
428
472
    return ShiftedZone;
429
4
  else 
if (4
!InclStart && 4
!InclEnd2
)
430
2
    return give(isl_union_map_intersect(Zone.take(), ShiftedZone.take()));
431
2
432
476
  assert(InclStart && InclEnd);
433
2
  return give(isl_union_map_union(Zone.take(), ShiftedZone.take()));
434
2
}
435
436
isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim,
437
58
                                        bool InclStart, bool InclEnd) {
438
58
  if (
!InclStart && 58
InclEnd58
)
439
58
    return Zone;
440
0
441
0
  auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
442
0
  if (
InclStart && 0
!InclEnd0
)
443
0
    return ShiftedZone;
444
0
  else 
if (0
!InclStart && 0
!InclEnd0
)
445
0
    return give(isl_map_intersect(Zone.take(), ShiftedZone.take()));
446
0
447
0
  assert(InclStart && InclEnd);
448
0
  return give(isl_map_union(Zone.take(), ShiftedZone.take()));
449
0
}
450
451
160
isl::map polly::distributeDomain(isl::map Map) {
452
160
  // Note that we cannot take Map apart into { Domain[] -> Range1[] } and {
453
160
  // Domain[] -> Range2[] } and combine again. We would loose any relation
454
160
  // between Range1[] and Range2[] that is not also a constraint to Domain[].
455
160
456
160
  auto Space = give(isl_map_get_space(Map.keep()));
457
160
  auto DomainSpace = give(isl_space_domain(Space.copy()));
458
160
  auto DomainDims = isl_space_dim(DomainSpace.keep(), isl_dim_set);
459
160
  auto RangeSpace = give(isl_space_unwrap(isl_space_range(Space.copy())));
460
160
  auto Range1Space = give(isl_space_domain(RangeSpace.copy()));
461
160
  auto Range1Dims = isl_space_dim(Range1Space.keep(), isl_dim_set);
462
160
  auto Range2Space = give(isl_space_range(RangeSpace.copy()));
463
160
  auto Range2Dims = isl_space_dim(Range2Space.keep(), isl_dim_set);
464
160
465
160
  auto OutputSpace = give(isl_space_map_from_domain_and_range(
466
160
      isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
467
160
                                                         Range1Space.copy())),
468
160
      isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
469
160
                                                         Range2Space.copy()))));
470
160
471
160
  auto Translator =
472
160
      give(isl_basic_map_universe(isl_space_map_from_domain_and_range(
473
160
          isl_space_wrap(Space.copy()), isl_space_wrap(OutputSpace.copy()))));
474
160
475
322
  for (unsigned i = 0; 
i < DomainDims322
;
i += 1162
) {
476
162
    Translator = give(
477
162
        isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out, i));
478
162
    Translator =
479
162
        give(isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out,
480
162
                                  DomainDims + Range1Dims + i));
481
162
  }
482
497
  for (unsigned i = 0; 
i < Range1Dims497
;
i += 1337
) {
483
337
    Translator =
484
337
        give(isl_basic_map_equate(Translator.take(), isl_dim_in, DomainDims + i,
485
337
                                  isl_dim_out, DomainDims + i));
486
337
  }
487
286
  for (unsigned i = 0; 
i < Range2Dims286
;
i += 1126
) {
488
126
    Translator = give(isl_basic_map_equate(
489
126
        Translator.take(), isl_dim_in, DomainDims + Range1Dims + i, isl_dim_out,
490
126
        DomainDims + Range1Dims + DomainDims + i));
491
126
  }
492
160
493
160
  return give(isl_set_unwrap(isl_set_apply(
494
160
      isl_map_wrap(Map.copy()), isl_map_from_basic_map(Translator.copy()))));
495
160
}
496
497
93
isl::union_map polly::distributeDomain(isl::union_map UMap) {
498
93
  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
499
158
  isl::stat Success = UMap.foreach_map([=, &Result](isl::map Map) {
500
158
    auto Distributed = distributeDomain(Map);
501
158
    Result = give(isl_union_map_add_map(Result.take(), Distributed.copy()));
502
158
    return isl::stat::ok;
503
158
  });
504
93
  if (Success != isl::stat::ok)
505
1
    return {};
506
92
  return Result;
507
92
}
508
509
42
isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {
510
42
511
42
  // { Factor[] -> Factor[] }
512
42
  auto Factors = makeIdentityMap(std::move(Factor), true);
513
42
514
42
  return std::move(Factors).product(std::move(UMap));
515
42
}
516
517
isl::union_map polly::applyDomainRange(isl::union_map UMap,
518
39
                                       isl::union_map Func) {
519
39
  // This implementation creates unnecessary cross products of the
520
39
  // DomainDomain[] and Func. An alternative implementation could reverse
521
39
  // domain+uncurry,apply Func to what now is the domain, then undo the
522
39
  // preparing transformation. Another alternative implementation could create a
523
39
  // translator map for each piece.
524
39
525
39
  // { DomainDomain[] }
526
39
  auto DomainDomain = UMap.domain().unwrap().domain();
527
39
528
39
  // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]]
529
39
  // }
530
39
  auto LifetedFunc = liftDomains(std::move(Func), DomainDomain);
531
39
532
39
  return std::move(UMap).apply_domain(std::move(LifetedFunc));
533
39
}
534
535
116
isl::map polly::intersectRange(isl::map Map, isl::union_set Range) {
536
116
  isl::set RangeSet = Range.extract_set(Map.get_space().range());
537
116
  return Map.intersect_range(RangeSet);
538
116
}