final/lib/Transform/FlattenAlgo.cpp

//===------ 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_space_params(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;
}