Coverage Report

Created: 2017-08-18 19:41

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Transform/FlattenAlgo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------ FlattenAlgo.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
// Main algorithm of the FlattenSchedulePass. This is a separate file to avoid
11
// the unittest for this requiring linking against LLVM.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "polly/FlattenAlgo.h"
16
#include "polly/Support/ISLOStream.h"
17
#include "llvm/Support/Debug.h"
18
#define DEBUG_TYPE "polly-flatten-algo"
19
20
using namespace polly;
21
using namespace llvm;
22
23
namespace {
24
25
/// Whether a dimension of a set is bounded (lower and upper) by a constant,
26
/// i.e. there are two constants Min and Max, such that every value x of the
27
/// chosen dimensions is Min <= x <= Max.
28
94
bool isDimBoundedByConstant(isl::set Set, unsigned dim) {
29
94
  auto ParamDims = Set.dim(isl::dim::param);
30
94
  Set = Set.project_out(isl::dim::param, 0, ParamDims);
31
94
  Set = Set.project_out(isl::dim::set, 0, dim);
32
94
  auto SetDims = Set.dim(isl::dim::set);
33
94
  Set = Set.project_out(isl::dim::set, 1, SetDims - 1);
34
94
  return bool(Set.is_bounded());
35
94
}
36
37
/// Whether a dimension of a set is (lower and upper) bounded by a constant or
38
/// parameters, i.e. there are two expressions Min_p and Max_p of the parameters
39
/// p, such that every value x of the chosen dimensions is
40
/// Min_p <= x <= Max_p.
41
94
bool isDimBoundedByParameter(isl::set Set, unsigned dim) {
42
94
  Set = Set.project_out(isl::dim::set, 0, dim);
43
94
  auto SetDims = Set.dim(isl::dim::set);
44
94
  Set = Set.project_out(isl::dim::set, 1, SetDims - 1);
45
94
  return bool(Set.is_bounded());
46
94
}
47
48
/// Whether BMap's first out-dimension is not a constant.
49
191
bool isVariableDim(const isl::basic_map &BMap) {
50
191
  auto FixedVal = BMap.plain_get_val_if_fixed(isl::dim::out, 0);
51
191
  return !FixedVal || FixedVal.is_nan();
52
191
}
53
54
/// Whether Map's first out dimension is no constant nor piecewise constant.
55
191
bool isVariableDim(const isl::map &Map) {
56
191
  return Map.foreach_basic_map([](isl::basic_map BMap) -> isl::stat {
57
191
    if (isVariableDim(BMap))
58
136
      return isl::stat::error;
59
55
    return isl::stat::ok;
60
191
  }) == isl::stat::ok;
61
191
}
62
63
/// Whether UMap's first out dimension is no (piecewise) constant.
64
93
bool isVariableDim(const isl::union_map &UMap) {
65
191
  return UMap.foreach_map([](isl::map Map) -> isl::stat {
66
191
    if (isVariableDim(Map))
67
55
      return isl::stat::error;
68
136
    return isl::stat::ok;
69
191
  }) == isl::stat::ok;
70
93
}
71
72
/// If @p PwAff maps to a constant, return said constant. If @p Max/@p Min, it
73
/// can also be a piecewise constant and it would return the minimum/maximum
74
/// value. Otherwise, return NaN.
75
74
isl::val getConstant(isl::pw_aff PwAff, bool Max, bool Min) {
76
74
  assert(!Max || !Min);
77
74
  isl::val Result;
78
74
  PwAff.foreach_piece([=, &Result](isl::set Set, isl::aff Aff) -> isl::stat {
79
74
    if (
Result && 74
Result.is_nan()0
)
80
0
      return isl::stat::ok;
81
74
82
74
    // TODO: If Min/Max, we can also determine a minimum/maximum value if
83
74
    // Set is constant-bounded.
84
74
    
if (74
!Aff.is_cst()74
)
{0
85
0
      Result = isl::val::nan(Aff.get_ctx());
86
0
      return isl::stat::error;
87
74
    }
88
74
89
74
    auto ThisVal = Aff.get_constant_val();
90
74
    if (
!Result74
)
{74
91
74
      Result = ThisVal;
92
74
      return isl::stat::ok;
93
74
    }
94
74
95
0
    
if (0
Result.eq(ThisVal)0
)
96
0
      return isl::stat::ok;
97
0
98
0
    
if (0
Max && 0
ThisVal.gt(Result)0
)
{0
99
0
      Result = ThisVal;
100
0
      return isl::stat::ok;
101
0
    }
102
0
103
0
    
if (0
Min && 0
ThisVal.lt(Result)0
)
{0
104
0
      Result = ThisVal;
105
0
      return isl::stat::ok;
106
0
    }
107
0
108
0
    // Not compatible
109
0
    Result = isl::val::nan(Aff.get_ctx());
110
0
    return isl::stat::error;
111
74
  });
112
74
  return Result;
113
74
}
114
115
/// Compute @p UPwAff - @p Val.
116
37
isl::union_pw_aff subtract(isl::union_pw_aff UPwAff, isl::val Val) {
117
37
  if (Val.is_zero())
118
37
    return UPwAff;
119
37
120
37
  auto Result = isl::union_pw_aff::empty(UPwAff.get_space());
121
0
  UPwAff.foreach_pw_aff([=, &Result](isl::pw_aff PwAff) -> isl::stat {
122
0
    auto ValAff =
123
0
        isl::pw_aff(isl::set::universe(PwAff.get_space().domain()), Val);
124
0
    auto Subtracted = PwAff.sub(ValAff);
125
0
    Result = Result.union_add(isl::union_pw_aff(Subtracted));
126
0
    return isl::stat::ok;
127
0
  });
128
37
  return Result;
129
37
}
130
131
/// Compute @UPwAff * @p Val.
132
37
isl::union_pw_aff multiply(isl::union_pw_aff UPwAff, isl::val Val) {
133
37
  if (Val.is_one())
134
1
    return UPwAff;
135
37
136
37
  auto Result = isl::union_pw_aff::empty(UPwAff.get_space());
137
130
  UPwAff.foreach_pw_aff([=, &Result](isl::pw_aff PwAff) -> isl::stat {
138
130
    auto ValAff =
139
130
        isl::pw_aff(isl::set::universe(PwAff.get_space().domain()), Val);
140
130
    auto Multiplied = PwAff.mul(ValAff);
141
130
    Result = Result.union_add(Multiplied);
142
130
    return isl::stat::ok;
143
130
  });
144
37
  return Result;
145
37
}
146
147
/// Remove @p n dimensions from @p UMap's range, starting at @p first.
148
///
149
/// It is assumed that all maps in the maps have at least the necessary number
150
/// of out dimensions.
151
isl::union_map scheduleProjectOut(const isl::union_map &UMap, unsigned first,
152
357
                                  unsigned n) {
153
357
  if (n == 0)
154
94
    return UMap; /* isl_map_project_out would also reset the tuple, which should
155
357
                    have no effect on schedule ranges */
156
357
157
357
  auto Result = isl::union_map::empty(UMap.get_space());
158
539
  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
159
539
    auto Outprojected = Map.project_out(isl::dim::out, first, n);
160
539
    Result = Result.add_map(Outprojected);
161
539
    return isl::stat::ok;
162
539
  });
163
357
  return Result;
164
357
}
165
166
/// Return the number of dimensions in the input map's range.
167
///
168
/// Because this function takes an isl_union_map, the out dimensions could be
169
/// different. We return the maximum number in this case. However, a different
170
/// number of dimensions is not supported by the other code in this file.
171
288
size_t scheduleScatterDims(const isl::union_map &Schedule) {
172
288
  unsigned Dims = 0;
173
633
  Schedule.foreach_map([&Dims](isl::map Map) -> isl::stat {
174
633
    Dims = std::max(Dims, Map.dim(isl::dim::out));
175
633
    return isl::stat::ok;
176
633
  });
177
288
  return Dims;
178
288
}
179
180
/// Return the @p pos' range dimension, converted to an isl_union_pw_aff.
181
168
isl::union_pw_aff scheduleExtractDimAff(isl::union_map UMap, unsigned pos) {
182
168
  auto SingleUMap = isl::union_map::empty(UMap.get_space());
183
398
  UMap.foreach_map([=, &SingleUMap](isl::map Map) -> isl::stat {
184
398
    auto MapDims = Map.dim(isl::dim::out);
185
398
    auto SingleMap = Map.project_out(isl::dim::out, 0, pos);
186
398
    SingleMap = SingleMap.project_out(isl::dim::out, 1, MapDims - pos - 1);
187
398
    SingleUMap = SingleUMap.add_map(SingleMap);
188
398
    return isl::stat::ok;
189
398
  });
190
168
191
168
  auto UAff = isl::union_pw_multi_aff(SingleUMap);
192
168
  auto FirstMAff = isl::multi_union_pw_aff(UAff);
193
168
  return FirstMAff.get_union_pw_aff(0);
194
168
}
195
196
/// Flatten a sequence-like first dimension.
197
///
198
/// A sequence-like scatter dimension is constant, or at least only small
199
/// variation, typically the result of ordering a sequence of different
200
/// statements. An example would be:
201
///   { Stmt_A[] -> [0, X, ...]; Stmt_B[] -> [1, Y, ...] }
202
/// to schedule all instances of Stmt_A before any instance of Stmt_B.
203
///
204
/// To flatten, first begin with an offset of zero. Then determine the lowest
205
/// possible value of the dimension, call it "i" [In the example we start at 0].
206
/// Considering only schedules with that value, consider only instances with
207
/// that value and determine the extent of the next dimension. Let l_X(i) and
208
/// u_X(i) its minimum (lower bound) and maximum (upper bound) value. Add them
209
/// as "Offset + X - l_X(i)" to the new schedule, then add "u_X(i) - l_X(i) + 1"
210
/// to Offset and remove all i-instances from the old schedule. Repeat with the
211
/// remaining lowest value i' until there are no instances in the old schedule
212
/// left.
213
/// The example schedule would be transformed to:
214
///   { Stmt_X[] -> [X - l_X, ...]; Stmt_B -> [l_X - u_X + 1 + Y - l_Y, ...] }
215
56
isl::union_map tryFlattenSequence(isl::union_map Schedule) {
216
56
  auto IslCtx = Schedule.get_ctx();
217
56
  auto ScatterSet = isl::set(Schedule.range());
218
56
219
56
  auto ParamSpace = Schedule.get_space().params();
220
56
  auto Dims = ScatterSet.dim(isl::dim::set);
221
56
  assert(Dims >= 2);
222
56
223
56
  // Would cause an infinite loop.
224
56
  if (
!isDimBoundedByConstant(ScatterSet, 0)56
)
{0
225
0
    DEBUG(dbgs() << "Abort; dimension is not of fixed size\n");
226
0
    return nullptr;
227
56
  }
228
56
229
56
  auto AllDomains = Schedule.domain();
230
56
  auto AllDomainsToNull = isl::union_pw_multi_aff(AllDomains);
231
56
232
56
  auto NewSchedule = isl::union_map::empty(ParamSpace);
233
56
  auto Counter = isl::pw_aff(isl::local_space(ParamSpace.set_from_params()));
234
56
235
150
  while (
!ScatterSet.is_empty()150
)
{94
236
94
    DEBUG(dbgs() << "Next counter:\n  " << Counter << "\n");
237
94
    DEBUG(dbgs() << "Remaining scatter set:\n  " << ScatterSet << "\n");
238
94
    auto ThisSet = ScatterSet.project_out(isl::dim::set, 1, Dims - 1);
239
94
    auto ThisFirst = ThisSet.lexmin();
240
94
    auto ScatterFirst = ThisFirst.add_dims(isl::dim::set, Dims - 1);
241
94
242
94
    auto SubSchedule = Schedule.intersect_range(ScatterFirst);
243
94
    SubSchedule = scheduleProjectOut(SubSchedule, 0, 1);
244
94
    SubSchedule = flattenSchedule(SubSchedule);
245
94
246
94
    auto SubDims = scheduleScatterDims(SubSchedule);
247
94
    auto FirstSubSchedule = scheduleProjectOut(SubSchedule, 1, SubDims - 1);
248
94
    auto FirstScheduleAff = scheduleExtractDimAff(FirstSubSchedule, 0);
249
94
    auto RemainingSubSchedule = scheduleProjectOut(SubSchedule, 0, 1);
250
94
251
94
    auto FirstSubScatter = isl::set(FirstSubSchedule.range());
252
94
    DEBUG(dbgs() << "Next step in sequence is:\n  " << FirstSubScatter << "\n");
253
94
254
94
    if (
!isDimBoundedByParameter(FirstSubScatter, 0)94
)
{0
255
0
      DEBUG(dbgs() << "Abort; sequence step is not bounded\n");
256
0
      return nullptr;
257
94
    }
258
94
259
94
    auto FirstSubScatterMap = isl::map::from_range(FirstSubScatter);
260
94
261
94
    // isl_set_dim_max returns a strange isl_pw_aff with domain tuple_id of
262
94
    // 'none'. It doesn't match with any space including a 0-dimensional
263
94
    // anonymous tuple.
264
94
    // Interesting, one can create such a set using
265
94
    // isl_set_universe(ParamSpace). Bug?
266
94
    auto PartMin = FirstSubScatterMap.dim_min(0);
267
94
    auto PartMax = FirstSubScatterMap.dim_max(0);
268
94
    auto One = isl::pw_aff(isl::set::universe(ParamSpace.set_from_params()),
269
94
                           isl::val::one(IslCtx));
270
94
    auto PartLen = PartMax.add(PartMin.neg()).add(One);
271
94
272
94
    auto AllPartMin = isl::union_pw_aff(PartMin).pullback(AllDomainsToNull);
273
94
    auto FirstScheduleAffNormalized = FirstScheduleAff.sub(AllPartMin);
274
94
    auto AllCounter = isl::union_pw_aff(Counter).pullback(AllDomainsToNull);
275
94
    auto FirstScheduleAffWithOffset =
276
94
        FirstScheduleAffNormalized.add(AllCounter);
277
94
278
94
    auto ScheduleWithOffset = isl::union_map(FirstScheduleAffWithOffset)
279
94
                                  .flat_range_product(RemainingSubSchedule);
280
94
    NewSchedule = NewSchedule.unite(ScheduleWithOffset);
281
94
282
94
    ScatterSet = ScatterSet.subtract(ScatterFirst);
283
94
    Counter = Counter.add(PartLen);
284
94
  }
285
56
286
56
  
DEBUG56
(dbgs() << "Sequence-flatten result is:\n " << NewSchedule << "\n");56
287
56
  return NewSchedule;
288
56
}
289
290
/// Flatten a loop-like first dimension.
291
///
292
/// A loop-like dimension is one that depends on a variable (usually a loop's
293
/// induction variable). Let the input schedule look like this:
294
///   { Stmt[i] -> [i, X, ...] }
295
///
296
/// To flatten, we determine the largest extent of X which may not depend on the
297
/// actual value of i. Let l_X() the smallest possible value of X and u_X() its
298
/// largest value. Then, construct a new schedule
299
///   { Stmt[i] -> [i * (u_X() - l_X() + 1), ...] }
300
38
isl::union_map tryFlattenLoop(isl::union_map Schedule) {
301
38
  assert(scheduleScatterDims(Schedule) >= 2);
302
38
303
38
  auto Remaining = scheduleProjectOut(Schedule, 0, 1);
304
38
  auto SubSchedule = flattenSchedule(Remaining);
305
38
  auto SubDims = scheduleScatterDims(SubSchedule);
306
38
307
38
  auto SubExtent = isl::set(SubSchedule.range());
308
38
  auto SubExtentDims = SubExtent.dim(isl::dim::param);
309
38
  SubExtent = SubExtent.project_out(isl::dim::param, 0, SubExtentDims);
310
38
  SubExtent = SubExtent.project_out(isl::dim::set, 1, SubDims - 1);
311
38
312
38
  if (
!isDimBoundedByConstant(SubExtent, 0)38
)
{1
313
1
    DEBUG(dbgs() << "Abort; dimension not bounded by constant\n");
314
1
    return nullptr;
315
38
  }
316
38
317
38
  auto Min = SubExtent.dim_min(0);
318
37
  DEBUG(dbgs() << "Min bound:\n  " << Min << "\n");
319
37
  auto MinVal = getConstant(Min, false, true);
320
37
  auto Max = SubExtent.dim_max(0);
321
37
  DEBUG(dbgs() << "Max bound:\n  " << Max << "\n");
322
37
  auto MaxVal = getConstant(Max, true, false);
323
37
324
37
  if (
!MinVal || 37
!MaxVal37
||
MinVal.is_nan()37
||
MaxVal.is_nan()37
)
{0
325
0
    DEBUG(dbgs() << "Abort; dimension bounds could not be determined\n");
326
0
    return nullptr;
327
37
  }
328
37
329
37
  auto FirstSubScheduleAff = scheduleExtractDimAff(SubSchedule, 0);
330
37
  auto RemainingSubSchedule = scheduleProjectOut(std::move(SubSchedule), 0, 1);
331
37
332
37
  auto LenVal = MaxVal.sub(MinVal).add_ui(1);
333
37
  auto FirstSubScheduleNormalized = subtract(FirstSubScheduleAff, MinVal);
334
37
335
37
  // TODO: Normalize FirstAff to zero (convert to isl_map, determine minimum,
336
37
  // subtract it)
337
37
  auto FirstAff = scheduleExtractDimAff(Schedule, 0);
338
37
  auto Offset = multiply(FirstAff, LenVal);
339
37
  auto Index = FirstSubScheduleNormalized.add(Offset);
340
37
  auto IndexMap = isl::union_map(Index);
341
37
342
37
  auto Result = IndexMap.flat_range_product(RemainingSubSchedule);
343
37
  DEBUG(dbgs() << "Loop-flatten result is:\n  " << Result << "\n");
344
37
  return Result;
345
38
}
346
} // anonymous namespace
347
348
156
isl::union_map polly::flattenSchedule(isl::union_map Schedule) {
349
156
  auto Dims = scheduleScatterDims(Schedule);
350
156
  DEBUG(dbgs() << "Recursive schedule to process:\n  " << Schedule << "\n");
351
156
352
156
  // Base case; no dimensions left
353
156
  if (
Dims == 0156
)
{0
354
0
    // TODO: Add one dimension?
355
0
    return Schedule;
356
156
  }
357
156
358
156
  // Base case; already one-dimensional
359
156
  
if (156
Dims == 1156
)
360
63
    return Schedule;
361
156
362
156
  // Fixed dimension; no need to preserve variabledness.
363
93
  
if (93
!isVariableDim(Schedule)93
)
{55
364
55
    DEBUG(dbgs() << "Fixed dimension; try sequence flattening\n");
365
55
    auto NewScheduleSequence = tryFlattenSequence(Schedule);
366
55
    if (NewScheduleSequence)
367
55
      return NewScheduleSequence;
368
93
  }
369
93
370
93
  // Constant stride
371
38
  
DEBUG38
(dbgs() << "Try loop flattening\n");38
372
38
  auto NewScheduleLoop = tryFlattenLoop(Schedule);
373
38
  if (NewScheduleLoop)
374
37
    return NewScheduleLoop;
375
38
376
38
  // Try again without loop condition (may blow up the number of pieces!!)
377
1
  
DEBUG1
(dbgs() << "Try sequence flattening again\n");1
378
1
  auto NewScheduleSequence = tryFlattenSequence(Schedule);
379
1
  if (NewScheduleSequence)
380
1
    return NewScheduleSequence;
381
1
382
1
  // Cannot flatten
383
0
  return Schedule;
384
156
}