Coverage Report

Created: 2019-04-21 11:35

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