diff options
Diffstat (limited to 'polly/lib/Transform/FlattenAlgo.cpp')
| -rw-r--r-- | polly/lib/Transform/FlattenAlgo.cpp | 417 |
1 files changed, 417 insertions, 0 deletions
diff --git a/polly/lib/Transform/FlattenAlgo.cpp b/polly/lib/Transform/FlattenAlgo.cpp new file mode 100644 index 00000000000..bd1ce4d24ee --- /dev/null +++ b/polly/lib/Transform/FlattenAlgo.cpp @@ -0,0 +1,417 @@ +//===------ FlattenAlgo.cpp ------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Main algorithm of the FlattenSchedulePass. This is a separate file to avoid +// the unittest for this requiring linking against LLVM. +// +//===----------------------------------------------------------------------===// + +#include "polly/FlattenAlgo.h" +#include "llvm/Support/Debug.h" +#define DEBUG_TYPE "polly-flatten-algo" + +using namespace polly; +using namespace llvm; + +namespace { + +/// Whether a dimension of a set is bounded (lower and upper) by a constant, +/// i.e. there are two constants Min and Max, such that every value x of the +/// chosen dimensions is Min <= x <= Max. +bool isDimBoundedByConstant(IslPtr<isl_set> Set, unsigned dim) { + auto ParamDims = isl_set_dim(Set.keep(), isl_dim_param); + Set = give(isl_set_project_out(Set.take(), isl_dim_param, 0, ParamDims)); + Set = give(isl_set_project_out(Set.take(), isl_dim_set, 0, dim)); + auto SetDims = isl_set_dim(Set.keep(), isl_dim_set); + Set = give(isl_set_project_out(Set.take(), isl_dim_set, 1, SetDims - 1)); + return isl_set_is_bounded(Set.keep()); +} + +/// Whether a dimension of a set is (lower and upper) bounded by a constant or +/// parameters, i.e. there are two expressions Min_p and Max_p of the parameters +/// p, such that every value x of the chosen dimensions is +/// Min_p <= x <= Max_p. +bool isDimBoundedByParameter(IslPtr<isl_set> Set, unsigned dim) { + Set = give(isl_set_project_out(Set.take(), isl_dim_set, 0, dim)); + auto SetDims = isl_set_dim(Set.keep(), isl_dim_set); + Set = give(isl_set_project_out(Set.take(), isl_dim_set, 1, SetDims - 1)); + return isl_set_is_bounded(Set.keep()); +} + +/// Whether BMap's first out-dimension is not a constant. +bool isVariableDim(NonowningIslPtr<isl_basic_map> BMap) { + auto FixedVal = + give(isl_basic_map_plain_get_val_if_fixed(BMap.keep(), isl_dim_out, 0)); + return !FixedVal || isl_val_is_nan(FixedVal.keep()); +} + +/// Whether Map's first out dimension is no constant nor piecewise constant. +bool isVariableDim(NonowningIslPtr<isl_map> Map) { + return foreachEltWithBreak(Map, [](IslPtr<isl_basic_map> BMap) -> isl_stat { + if (isVariableDim(BMap)) + return isl_stat_error; + return isl_stat_ok; + }); +} + +/// Whether UMap's first out dimension is no (piecewise) constant. +bool isVariableDim(NonowningIslPtr<isl_union_map> UMap) { + return foreachEltWithBreak(UMap, [](IslPtr<isl_map> Map) -> isl_stat { + if (isVariableDim(Map)) + return isl_stat_error; + return isl_stat_ok; + }); +} + +/// If @p PwAff maps to a constant, return said constant. If @p Max/@p Min, it +/// can also be a piecewise constant and it would return the minimum/maximum +/// value. Otherwise, return NaN. +IslPtr<isl_val> getConstant(IslPtr<isl_pw_aff> PwAff, bool Max, bool Min) { + assert(!Max || !Min); + IslPtr<isl_val> Result; + foreachPieceWithBreak( + PwAff, [=, &Result](IslPtr<isl_set> Set, IslPtr<isl_aff> Aff) { + if (Result && isl_val_is_nan(Result.keep())) + return isl_stat_ok; + + // TODO: If Min/Max, we can also determine a minimum/maximum value if + // Set is constant-bounded. + if (!isl_aff_is_cst(Aff.keep())) { + Result = give(isl_val_nan(Aff.getCtx())); + return isl_stat_error; + } + + auto ThisVal = give(isl_aff_get_constant_val(Aff.keep())); + if (!Result) { + Result = ThisVal; + return isl_stat_ok; + } + + if (isl_val_eq(Result.keep(), ThisVal.keep())) + return isl_stat_ok; + + if (Max && isl_val_gt(ThisVal.keep(), Result.keep())) { + Result = ThisVal; + return isl_stat_ok; + } + + if (Min && isl_val_lt(ThisVal.keep(), Result.keep())) { + Result = ThisVal; + return isl_stat_ok; + } + + // Not compatible + Result = give(isl_val_nan(Aff.getCtx())); + return isl_stat_error; + }); + return Result; +} + +/// Compute @p UPwAff - @p Val. +IslPtr<isl_union_pw_aff> subtract(IslPtr<isl_union_pw_aff> UPwAff, + IslPtr<isl_val> Val) { + if (isl_val_is_zero(Val.keep())) + return UPwAff; + + auto Result = + give(isl_union_pw_aff_empty(isl_union_pw_aff_get_space(UPwAff.keep()))); + foreachElt(UPwAff, [=, &Result](IslPtr<isl_pw_aff> PwAff) { + auto ValAff = give(isl_pw_aff_val_on_domain( + isl_set_universe(isl_space_domain(isl_pw_aff_get_space(PwAff.keep()))), + Val.copy())); + auto Subtracted = give(isl_pw_aff_sub(PwAff.copy(), ValAff.take())); + Result = give(isl_union_pw_aff_union_add( + Result.take(), isl_union_pw_aff_from_pw_aff(Subtracted.take()))); + }); + return Result; +} + +/// Compute @UPwAff * @p Val. +IslPtr<isl_union_pw_aff> multiply(IslPtr<isl_union_pw_aff> UPwAff, + IslPtr<isl_val> Val) { + if (isl_val_is_one(Val.keep())) + return UPwAff; + + auto Result = + give(isl_union_pw_aff_empty(isl_union_pw_aff_get_space(UPwAff.keep()))); + foreachElt(UPwAff, [=, &Result](IslPtr<isl_pw_aff> PwAff) { + auto ValAff = give(isl_pw_aff_val_on_domain( + isl_set_universe(isl_space_domain(isl_pw_aff_get_space(PwAff.keep()))), + Val.copy())); + auto Multiplied = give(isl_pw_aff_mul(PwAff.copy(), ValAff.take())); + Result = give(isl_union_pw_aff_union_add( + Result.take(), isl_union_pw_aff_from_pw_aff(Multiplied.take()))); + }); + return Result; +} + +/// Remove @p n dimensions from @p UMap's range, starting at @p first. +/// +/// It is assumed that all maps in the maps have at least the necessary number +/// of out dimensions. +IslPtr<isl_union_map> scheduleProjectOut(NonowningIslPtr<isl_union_map> UMap, + unsigned first, unsigned n) { + if (n == 0) + return UMap; /* isl_map_project_out would also reset the tuple, which should + have no effect on schedule ranges */ + + auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep()))); + foreachElt(UMap, [=, &Result](IslPtr<isl_map> Map) { + auto Outprojected = + give(isl_map_project_out(Map.take(), isl_dim_out, first, n)); + Result = give(isl_union_map_add_map(Result.take(), Outprojected.take())); + }); + return Result; +} + +/// Return the number of dimensions in the input map's range. +/// +/// Because this function takes an isl_union_map, the out dimensions could be +/// different. We return the maximum number in this case. However, a different +/// number of dimensions is not supported by the other code in this file. +size_t scheduleScatterDims(NonowningIslPtr<isl_union_map> Schedule) { + unsigned Dims = 0; + foreachElt(Schedule, [&Dims](IslPtr<isl_map> Map) { + Dims = std::max(Dims, isl_map_dim(Map.keep(), isl_dim_out)); + }); + return Dims; +} + +/// Return the @p pos' range dimension, converted to an isl_union_pw_aff. +IslPtr<isl_union_pw_aff> scheduleExtractDimAff(IslPtr<isl_union_map> UMap, + unsigned pos) { + auto SingleUMap = + give(isl_union_map_empty(isl_union_map_get_space(UMap.keep()))); + foreachElt(UMap, [=, &SingleUMap](IslPtr<isl_map> Map) { + auto MapDims = isl_map_dim(Map.keep(), isl_dim_out); + auto SingleMap = give(isl_map_project_out(Map.take(), isl_dim_out, 0, pos)); + SingleMap = give(isl_map_project_out(SingleMap.take(), isl_dim_out, 1, + MapDims - pos - 1)); + SingleUMap = + give(isl_union_map_add_map(SingleUMap.take(), SingleMap.take())); + }); + + auto UAff = give(isl_union_pw_multi_aff_from_union_map(SingleUMap.take())); + auto FirstMAff = + give(isl_multi_union_pw_aff_from_union_pw_multi_aff(UAff.take())); + return give(isl_multi_union_pw_aff_get_union_pw_aff(FirstMAff.keep(), 0)); +} + +/// Flatten a sequence-like first dimension. +/// +/// A sequence-like scatter dimension is constant, or at least only small +/// variation, typically the result of ordering a sequence of different +/// statements. An example would be: +/// { Stmt_A[] -> [0, X, ...]; Stmt_B[] -> [1, Y, ...] } +/// to schedule all instances of Stmt_A before any instance of Stmt_B. +/// +/// To flatten, first begin with an offset of zero. Then determine the lowest +/// possible value of the dimension, call it "i" [In the example we start at 0]. +/// Considering only schedules with that value, consider only instances with +/// that value and determine the extent of the next dimension. Let l_X(i) and +/// u_X(i) its minimum (lower bound) and maximum (upper bound) value. Add them +/// as "Offset + X - l_X(i)" to the new schedule, then add "u_X(i) - l_X(i) + 1" +/// to Offset and remove all i-instances from the old schedule. Repeat with the +/// remaining lowest value i' until there are no instances in the old schedule +/// left. +/// The example schedule would be transformed to: +/// { Stmt_X[] -> [X - l_X, ...]; Stmt_B -> [l_X - u_X + 1 + Y - l_Y, ...] } +IslPtr<isl_union_map> tryFlattenSequence(IslPtr<isl_union_map> Schedule) { + auto IslCtx = Schedule.getCtx(); + auto ScatterSet = + give(isl_set_from_union_set(isl_union_map_range(Schedule.copy()))); + + auto ParamSpace = give(isl_union_map_get_space(Schedule.keep())); + auto Dims = isl_set_dim(ScatterSet.keep(), isl_dim_set); + assert(Dims >= 2); + + // Would cause an infinite loop. + if (!isDimBoundedByConstant(ScatterSet, 0)) { + DEBUG(dbgs() << "Abort; dimension is not of fixed size\n"); + return nullptr; + } + + auto AllDomains = give(isl_union_map_domain(Schedule.copy())); + auto AllDomainsToNull = + give(isl_union_pw_multi_aff_from_domain(AllDomains.take())); + + auto NewSchedule = give(isl_union_map_empty(ParamSpace.copy())); + auto Counter = give(isl_pw_aff_zero_on_domain(isl_local_space_from_space( + isl_space_set_from_params(ParamSpace.copy())))); + + while (!isl_set_is_empty(ScatterSet.keep())) { + DEBUG(dbgs() << "Next counter:\n " << Counter << "\n"); + DEBUG(dbgs() << "Remaining scatter set:\n " << ScatterSet << "\n"); + auto ThisSet = + give(isl_set_project_out(ScatterSet.copy(), isl_dim_set, 1, Dims - 1)); + auto ThisFirst = give(isl_set_lexmin(ThisSet.take())); + auto ScatterFirst = + give(isl_set_add_dims(ThisFirst.take(), isl_dim_set, Dims - 1)); + + auto SubSchedule = give(isl_union_map_intersect_range( + Schedule.copy(), isl_union_set_from_set(ScatterFirst.copy()))); + SubSchedule = scheduleProjectOut(std::move(SubSchedule), 0, 1); + SubSchedule = flattenSchedule(std::move(SubSchedule)); + + auto SubDims = scheduleScatterDims(SubSchedule); + auto FirstSubSchedule = scheduleProjectOut(SubSchedule, 1, SubDims - 1); + auto FirstScheduleAff = scheduleExtractDimAff(FirstSubSchedule, 0); + auto RemainingSubSchedule = + scheduleProjectOut(std::move(SubSchedule), 0, 1); + + auto FirstSubScatter = give( + isl_set_from_union_set(isl_union_map_range(FirstSubSchedule.take()))); + DEBUG(dbgs() << "Next step in sequence is:\n " << FirstSubScatter << "\n"); + + if (!isDimBoundedByParameter(FirstSubScatter, 0)) { + DEBUG(dbgs() << "Abort; sequence step is not bounded\n"); + return nullptr; + } + + auto FirstSubScatterMap = give(isl_map_from_range(FirstSubScatter.take())); + + // isl_set_dim_max returns a strange isl_pw_aff with domain tuple_id of + // 'none'. It doesn't match with any space including a 0-dimensional + // anonymous tuple. + // Interesting, one can create such a set using + // isl_set_universe(ParamSpace). Bug? + auto PartMin = give(isl_map_dim_min(FirstSubScatterMap.copy(), 0)); + auto PartMax = give(isl_map_dim_max(FirstSubScatterMap.take(), 0)); + auto One = give(isl_pw_aff_val_on_domain( + isl_set_universe(isl_space_set_from_params(ParamSpace.copy())), + isl_val_one(IslCtx))); + auto PartLen = give(isl_pw_aff_add( + isl_pw_aff_add(PartMax.take(), isl_pw_aff_neg(PartMin.copy())), + One.take())); + + auto AllPartMin = give(isl_union_pw_aff_pullback_union_pw_multi_aff( + isl_union_pw_aff_from_pw_aff(PartMin.take()), AllDomainsToNull.copy())); + auto FirstScheduleAffNormalized = + give(isl_union_pw_aff_sub(FirstScheduleAff.take(), AllPartMin.take())); + auto AllCounter = give(isl_union_pw_aff_pullback_union_pw_multi_aff( + isl_union_pw_aff_from_pw_aff(Counter.copy()), AllDomainsToNull.copy())); + auto FirstScheduleAffWithOffset = give(isl_union_pw_aff_add( + FirstScheduleAffNormalized.take(), AllCounter.take())); + + auto ScheduleWithOffset = give(isl_union_map_flat_range_product( + isl_union_map_from_union_pw_aff(FirstScheduleAffWithOffset.take()), + RemainingSubSchedule.take())); + NewSchedule = give( + isl_union_map_union(NewSchedule.take(), ScheduleWithOffset.take())); + + ScatterSet = give(isl_set_subtract(ScatterSet.take(), ScatterFirst.take())); + Counter = give(isl_pw_aff_add(Counter.take(), PartLen.take())); + } + + DEBUG(dbgs() << "Sequence-flatten result is:\n " << NewSchedule << "\n"); + return NewSchedule; +} + +/// Flatten a loop-like first dimension. +/// +/// A loop-like dimension is one that depends on a variable (usually a loop's +/// induction variable). Let the input schedule look like this: +/// { Stmt[i] -> [i, X, ...] } +/// +/// To flatten, we determine the largest extent of X which may not depend on the +/// actual value of i. Let l_X() the smallest possible value of X and u_X() its +/// largest value. Then, construct a new schedule +/// { Stmt[i] -> [i * (u_X() - l_X() + 1), ...] } +IslPtr<isl_union_map> tryFlattenLoop(IslPtr<isl_union_map> Schedule) { + assert(scheduleScatterDims(Schedule) >= 2); + + auto Remaining = scheduleProjectOut(Schedule, 0, 1); + auto SubSchedule = flattenSchedule(Remaining); + auto SubDims = scheduleScatterDims(SubSchedule); + + auto SubExtent = + give(isl_set_from_union_set(isl_union_map_range(SubSchedule.copy()))); + auto SubExtentDims = isl_set_dim(SubExtent.keep(), isl_dim_param); + SubExtent = give( + isl_set_project_out(SubExtent.take(), isl_dim_param, 0, SubExtentDims)); + SubExtent = + give(isl_set_project_out(SubExtent.take(), isl_dim_set, 1, SubDims - 1)); + + if (!isDimBoundedByConstant(SubExtent, 0)) { + DEBUG(dbgs() << "Abort; dimension not bounded by constant\n"); + return nullptr; + } + + auto Min = give(isl_set_dim_min(SubExtent.copy(), 0)); + DEBUG(dbgs() << "Min bound:\n " << Min << "\n"); + auto MinVal = getConstant(Min, false, true); + auto Max = give(isl_set_dim_max(SubExtent.take(), 0)); + DEBUG(dbgs() << "Max bound:\n " << Max << "\n"); + auto MaxVal = getConstant(Max, true, false); + + if (!MinVal || !MaxVal || isl_val_is_nan(MinVal.keep()) || + isl_val_is_nan(MaxVal.keep())) { + DEBUG(dbgs() << "Abort; dimension bounds could not be determined\n"); + return nullptr; + } + + auto FirstSubScheduleAff = scheduleExtractDimAff(SubSchedule, 0); + auto RemainingSubSchedule = scheduleProjectOut(std::move(SubSchedule), 0, 1); + + auto LenVal = + give(isl_val_add_ui(isl_val_sub(MaxVal.take(), MinVal.copy()), 1)); + auto FirstSubScheduleNormalized = subtract(FirstSubScheduleAff, MinVal); + + // TODO: Normalize FirstAff to zero (convert to isl_map, determine minimum, + // subtract it) + auto FirstAff = scheduleExtractDimAff(Schedule, 0); + auto Offset = multiply(FirstAff, LenVal); + auto Index = give( + isl_union_pw_aff_add(FirstSubScheduleNormalized.take(), Offset.take())); + auto IndexMap = give(isl_union_map_from_union_pw_aff(Index.take())); + + auto Result = give(isl_union_map_flat_range_product( + IndexMap.take(), RemainingSubSchedule.take())); + DEBUG(dbgs() << "Loop-flatten result is:\n " << Result << "\n"); + return Result; +} +} // anonymous namespace + +IslPtr<isl_union_map> polly::flattenSchedule(IslPtr<isl_union_map> Schedule) { + auto Dims = scheduleScatterDims(Schedule); + DEBUG(dbgs() << "Recursive schedule to process:\n " << Schedule << "\n"); + + // Base case; no dimensions left + if (Dims == 0) { + // TODO: Add one dimension? + return Schedule; + } + + // Base case; already one-dimensional + if (Dims == 1) + return Schedule; + + // Fixed dimension; no need to preserve variabledness. + if (!isVariableDim(Schedule)) { + DEBUG(dbgs() << "Fixed dimension; try sequence flattening\n"); + auto NewScheduleSequence = tryFlattenSequence(Schedule); + if (NewScheduleSequence) + return NewScheduleSequence; + } + + // Constant stride + DEBUG(dbgs() << "Try loop flattening\n"); + auto NewScheduleLoop = tryFlattenLoop(Schedule); + if (NewScheduleLoop) + return NewScheduleLoop; + + // Try again without loop condition (may blow up the number of pieces!!) + DEBUG(dbgs() << "Try sequence flattening again\n"); + auto NewScheduleSequence = tryFlattenSequence(Schedule); + if (NewScheduleSequence) + return NewScheduleSequence; + + // Cannot flatten + return Schedule; +} |
