Coverage Report

Created: 2017-08-18 19:41

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