ISLTools.cpp | Explore in Territory

//===------ ISLTools.cpp ----------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Tools, utilities, helpers and extensions useful in conjunction with the
// Integer Set Library (isl).
//
//===----------------------------------------------------------------------===//

#include "polly/Support/ISLTools.h"
#include "polly/Support/GICHelper.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <vector>

usingnamespacepolly;

namespace {
/// Create a map that shifts one dimension by an offset.
///
/// Example:
/// makeShiftDimAff({ [i0, i1] -> [o0, o1] }, 1, -2)
///   = { [i0, i1] -> [i0, i1 - 1] }
///
/// @param Space  The map space of the result. Must have equal number of in- and
///               out-dimensions.
/// @param Pos    Position to shift.
/// @param Amount Value added to the shifted dimension.
///
/// @return An isl_multi_aff for the map with this shifted dimension.
isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) { … }

/// Construct a map that swaps two nested tuples.
///
/// @param FromSpace1 { Space1[] }
/// @param FromSpace2 { Space2[] }
///
/// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1,
                                     isl::space FromSpace2) { … }

/// Like makeTupleSwapBasicMap(isl::space,isl::space), but returns
/// an isl_map.
isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) { … }
} // anonymous namespace

isl::map polly::beforeScatter(isl::map Map, bool Strict) { … }

isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) { … }

isl::map polly::afterScatter(isl::map Map, bool Strict) { … }

isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) { … }

isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,
                               bool InclTo) { … }

isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To,
                                     bool InclFrom, bool InclTo) { … }

isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) { … }

isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) { … }

unsigned polly::getNumScatterDims(const isl::union_map &Schedule) { … }

isl::space polly::getScatterSpace(const isl::union_map &Schedule) { … }

isl::map polly::makeIdentityMap(const isl::set &Set, bool RestrictDomain) { … }

isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
                                      bool RestrictDomain) { … }

isl::map polly::reverseDomain(isl::map Map) { … }

isl::union_map polly::reverseDomain(const isl::union_map &UMap) { … }

isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) { … }

isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) { … }

isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) { … }

isl::val polly::getConstant(isl::map Map, isl::dim Dim, int Pos) { … }

isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
                               int Amount) { … }

void polly::simplify(isl::set &Set) { … }

void polly::simplify(isl::union_set &USet) { … }

void polly::simplify(isl::map &Map) { … }

void polly::simplify(isl::union_map &UMap) { … }

isl::union_map polly::computeReachingWrite(isl::union_map Schedule,
                                           isl::union_map Writes, bool Reverse,
                                           bool InclPrevDef, bool InclNextDef) { … }

isl::union_map
polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,
                          isl::union_map Reads, bool ReadEltInSameInst,
                          bool IncludeLastRead, bool IncludeWrite) { … }

isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
                                              bool InclStart, bool InclEnd) { … }

isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
                                              bool InclStart, bool InclEnd) { … }

isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim,
                                        bool InclStart, bool InclEnd) { … }

isl::map polly::distributeDomain(isl::map Map) { … }

isl::union_map polly::distributeDomain(isl::union_map UMap) { … }

isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) { … }

isl::union_map polly::applyDomainRange(isl::union_map UMap,
                                       isl::union_map Func) { … }

isl::map polly::intersectRange(isl::map Map, isl::union_set Range) { … }

isl::map polly::subtractParams(isl::map Map, isl::set Params) { … }

isl::set polly::subtractParams(isl::set Set, isl::set Params) { … }

isl::val polly::getConstant(isl::pw_aff PwAff, bool Max, bool Min) { … }

llvm::iota_range<unsigned> polly::rangeIslSize(unsigned Begin, isl::size End) { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
static void foreachPoint(const isl::set &Set,
                         const std::function<void(isl::point P)> &F) {
  Set.foreach_point([&](isl::point P) -> isl::stat {
    F(P);
    return isl::stat::ok();
  });
}

static void foreachPoint(isl::basic_set BSet,
                         const std::function<void(isl::point P)> &F) {
  foreachPoint(isl::set(BSet), F);
}

/// Determine the sorting order of the sets @p A and @p B without considering
/// the space structure.
///
/// Ordering is based on the lower bounds of the set's dimensions. First
/// dimensions are considered first.
static int flatCompare(const isl::basic_set &A, const isl::basic_set &B) {
  // Quick bail-out on out-of-quota.
  if (A.is_null() || B.is_null())
    return 0;

  unsigned ALen = unsignedFromIslSize(A.dim(isl::dim::set));
  unsigned BLen = unsignedFromIslSize(B.dim(isl::dim::set));
  unsigned Len = std::min(ALen, BLen);

  for (unsigned i = 0; i < Len; i += 1) {
    isl::basic_set ADim =
        A.project_out(isl::dim::param, 0,
                      unsignedFromIslSize(A.dim(isl::dim::param)))
            .project_out(isl::dim::set, i + 1, ALen - i - 1)
            .project_out(isl::dim::set, 0, i);
    isl::basic_set BDim =
        B.project_out(isl::dim::param, 0,
                      unsignedFromIslSize(B.dim(isl::dim::param)))
            .project_out(isl::dim::set, i + 1, BLen - i - 1)
            .project_out(isl::dim::set, 0, i);

    isl::basic_set AHull = isl::set(ADim).convex_hull();
    isl::basic_set BHull = isl::set(BDim).convex_hull();

    bool ALowerBounded =
        bool(isl::set(AHull).dim_has_any_lower_bound(isl::dim::set, 0));
    bool BLowerBounded =
        bool(isl::set(BHull).dim_has_any_lower_bound(isl::dim::set, 0));

    int BoundedCompare = BLowerBounded - ALowerBounded;
    if (BoundedCompare != 0)
      return BoundedCompare;

    if (!ALowerBounded || !BLowerBounded)
      continue;

    isl::pw_aff AMin = isl::set(ADim).dim_min(0);
    isl::pw_aff BMin = isl::set(BDim).dim_min(0);

    isl::val AMinVal = polly::getConstant(AMin, false, true);
    isl::val BMinVal = polly::getConstant(BMin, false, true);

    int MinCompare = AMinVal.sub(BMinVal).sgn();
    if (MinCompare != 0)
      return MinCompare;
  }

  // If all the dimensions' lower bounds are equal or incomparable, sort based
  // on the number of dimensions.
  return ALen - BLen;
}

/// Compare the sets @p A and @p B according to their nested space structure.
/// Returns 0 if the structure is considered equal.
/// If @p ConsiderTupleLen is false, the number of dimensions in a tuple are
/// ignored, i.e. a tuple with the same name but different number of dimensions
/// are considered equal.
static int structureCompare(const isl::space &ASpace, const isl::space &BSpace,
                            bool ConsiderTupleLen) {
  int WrappingCompare = bool(ASpace.is_wrapping()) - bool(BSpace.is_wrapping());
  if (WrappingCompare != 0)
    return WrappingCompare;

  if (ASpace.is_wrapping() && BSpace.is_wrapping()) {
    isl::space AMap = ASpace.unwrap();
    isl::space BMap = BSpace.unwrap();

    int FirstResult =
        structureCompare(AMap.domain(), BMap.domain(), ConsiderTupleLen);
    if (FirstResult != 0)
      return FirstResult;

    return structureCompare(AMap.range(), BMap.range(), ConsiderTupleLen);
  }

  std::string AName;
  if (!ASpace.is_params() && ASpace.has_tuple_name(isl::dim::set))
    AName = ASpace.get_tuple_name(isl::dim::set);

  std::string BName;
  if (!BSpace.is_params() && BSpace.has_tuple_name(isl::dim::set))
    BName = BSpace.get_tuple_name(isl::dim::set);

  int NameCompare = AName.compare(BName);
  if (NameCompare != 0)
    return NameCompare;

  if (ConsiderTupleLen) {
    int LenCompare = (int)unsignedFromIslSize(BSpace.dim(isl::dim::set)) -
                     (int)unsignedFromIslSize(ASpace.dim(isl::dim::set));
    if (LenCompare != 0)
      return LenCompare;
  }

  return 0;
}

/// Compare the sets @p A and @p B according to their nested space structure. If
/// the structure is the same, sort using the dimension lower bounds.
/// Returns an std::sort compatible bool.
static bool orderComparer(const isl::basic_set &A, const isl::basic_set &B) {
  isl::space ASpace = A.get_space();
  isl::space BSpace = B.get_space();

  // Ignoring number of dimensions first ensures that structures with same tuple
  // names, but different number of dimensions are still sorted close together.
  int TupleNestingCompare = structureCompare(ASpace, BSpace, false);
  if (TupleNestingCompare != 0)
    return TupleNestingCompare < 0;

  int TupleCompare = structureCompare(ASpace, BSpace, true);
  if (TupleCompare != 0)
    return TupleCompare < 0;

  return flatCompare(A, B) < 0;
}

/// Print a string representation of @p USet to @p OS.
///
/// The pieces of @p USet are printed in a sorted order. Spaces with equal or
/// similar nesting structure are printed together. Compared to isl's own
/// printing function the uses the structure itself as base of the sorting, not
/// a hash of it. It ensures that e.g. maps spaces with same domain structure
/// are printed together. Set pieces with same structure are printed in order of
/// their lower bounds.
///
/// @param USet     Polyhedra to print.
/// @param OS       Target stream.
/// @param Simplify Whether to simplify the polyhedron before printing.
/// @param IsMap    Whether @p USet is a wrapped map. If true, sets are
///                 unwrapped before printing to again appear as a map.
static void printSortedPolyhedra(isl::union_set USet, llvm::raw_ostream &OS,
                                 bool Simplify, bool IsMap) {
  if (USet.is_null()) {
    OS << "<null>\n";
    return;
  }

  if (Simplify)
    simplify(USet);

  // Get all the polyhedra.
  std::vector<isl::basic_set> BSets;

  for (isl::set Set : USet.get_set_list()) {
    for (isl::basic_set BSet : Set.get_basic_set_list()) {
      BSets.push_back(BSet);
    }
  }

  if (BSets.empty()) {
    OS << "{\n}\n";
    return;
  }

  // Sort the polyhedra.
  llvm::sort(BSets, orderComparer);

  // Print the polyhedra.
  bool First = true;
  for (const isl::basic_set &BSet : BSets) {
    std::string Str;
    if (IsMap)
      Str = stringFromIslObj(isl::map(BSet.unwrap()));
    else
      Str = stringFromIslObj(isl::set(BSet));
    size_t OpenPos = Str.find_first_of('{');
    assert(OpenPos != std::string::npos);
    size_t ClosePos = Str.find_last_of('}');
    assert(ClosePos != std::string::npos);

    if (First)
      OS << llvm::StringRef(Str).substr(0, OpenPos + 1) << "\n ";
    else
      OS << ";\n ";

    OS << llvm::StringRef(Str).substr(OpenPos + 1, ClosePos - OpenPos - 2);
    First = false;
  }
  assert(!First);
  OS << "\n}\n";
}

static void recursiveExpand(isl::basic_set BSet, unsigned Dim,
                            isl::set &Expanded) {
  unsigned Dims = unsignedFromIslSize(BSet.dim(isl::dim::set));
  if (Dim >= Dims) {
    Expanded = Expanded.unite(BSet);
    return;
  }

  isl::basic_set DimOnly =
      BSet.project_out(isl::dim::param, 0,
                       unsignedFromIslSize(BSet.dim(isl::dim::param)))
          .project_out(isl::dim::set, Dim + 1, Dims - Dim - 1)
          .project_out(isl::dim::set, 0, Dim);
  if (!DimOnly.is_bounded()) {
    recursiveExpand(BSet, Dim + 1, Expanded);
    return;
  }

  foreachPoint(DimOnly, [&, Dim](isl::point P) {
    isl::val Val = P.get_coordinate_val(isl::dim::set, 0);
    isl::basic_set FixBSet = BSet.fix_val(isl::dim::set, Dim, Val);
    recursiveExpand(FixBSet, Dim + 1, Expanded);
  });
}

/// Make each point of a set explicit.
///
/// "Expanding" makes each point a set contains explicit. That is, the result is
/// a set of singleton polyhedra. Unbounded dimensions are not expanded.
///
/// Example:
///   { [i] : 0 <= i < 2 }
/// is expanded to:
///   { [0]; [1] }
static isl::set expand(const isl::set &Set) {
  isl::set Expanded = isl::set::empty(Set.get_space());
  for (isl::basic_set BSet : Set.get_basic_set_list())
    recursiveExpand(BSet, 0, Expanded);
  return Expanded;
}

/// Expand all points of a union set explicit.
///
/// @see expand(const isl::set)
static isl::union_set expand(const isl::union_set &USet) {
  isl::union_set Expanded = isl::union_set::empty(USet.ctx());
  for (isl::set Set : USet.get_set_list()) {
    isl::set SetExpanded = expand(Set);
    Expanded = Expanded.unite(SetExpanded);
  }
  return Expanded;
}

LLVM_DUMP_METHOD void polly::dumpPw(const isl::set &Set) {
  printSortedPolyhedra(Set, llvm::errs(), true, false);
}

LLVM_DUMP_METHOD void polly::dumpPw(const isl::map &Map) {
  printSortedPolyhedra(Map.wrap(), llvm::errs(), true, true);
}

LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_set &USet) {
  printSortedPolyhedra(USet, llvm::errs(), true, false);
}

LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_map &UMap) {
  printSortedPolyhedra(UMap.wrap(), llvm::errs(), true, true);
}

LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_set *Set) {
  dumpPw(isl::manage_copy(Set));
}

LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_map *Map) {
  dumpPw(isl::manage_copy(Map));
}

LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_set *USet) {
  dumpPw(isl::manage_copy(USet));
}

LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_map *UMap) {
  dumpPw(isl::manage_copy(UMap));
}

LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::set &Set) {
  printSortedPolyhedra(expand(Set), llvm::errs(), false, false);
}

LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::map &Map) {
  printSortedPolyhedra(expand(Map.wrap()), llvm::errs(), false, true);
}

LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_set &USet) {
  printSortedPolyhedra(expand(USet), llvm::errs(), false, false);
}

LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_map &UMap) {
  printSortedPolyhedra(expand(UMap.wrap()), llvm::errs(), false, true);
}

LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_set *Set) {
  dumpExpanded(isl::manage_copy(Set));
}

LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_map *Map) {
  dumpExpanded(isl::manage_copy(Map));
}

LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_set *USet) {
  dumpExpanded(isl::manage_copy(USet));
}

LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_map *UMap) {
  dumpExpanded(isl::manage_copy(UMap));
}
#endif
llvm/polly/lib/Support/ISLTools.cpp
