Coverage Report

Created: 2017-11-21 16:49

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