Coverage Report

Created: 2017-04-27 19:33

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