[Support] Add general isl tools for DeLICM. NFC.

Add some generally useful isl tools into a their own new ISLTools.cpp.
These are the helpers were extracted from and will be use by the DeLICM
algorithm (https://reviews.llvm.org/D24716).

Suggested-by: 	Tobias Grosser <tobias@grosser.es>
llvm-svn: 293340

4 files changed, 741 insertions, 0 deletions

diff --git a/polly/include/polly/Support/ISLTools.h b/polly/include/polly/Support/ISLTools.h
new file mode 100644
index 00000000000..f0fb8d9deac
--- /dev/null
+++ b/polly/include/polly/Support/ISLTools.h
@@ -0,0 +1,180 @@
+//===------ ISLTools.h ------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Tools, utilities, helpers and extensions useful in conjunction with the
+// Integer Set Library (isl).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_ISLTOOLS_H
+#define POLLY_ISLTOOLS_H
+
+#include "polly/Support/GICHelper.h"
+
+namespace polly {
+
+/// Return the range elements that are lexicographically smaller.
+///
+/// @param Map    { Space[] -> Scatter[] }
+/// @param Strict True for strictly lexicographically smaller elements (exclude
+///               same timepoints from the result).
+///
+/// @return { Space[] -> Scatter[] }
+///         A map to all timepoints that happen before the timepoints the input
+///         mapped to.
+IslPtr<isl_map> beforeScatter(IslPtr<isl_map> Map, bool Strict);
+
+/// Piecewise beforeScatter(IslPtr<isl_map>,bool).
+IslPtr<isl_union_map> beforeScatter(IslPtr<isl_union_map> UMap, bool Strict);
+
+/// Return the range elements that are lexicographically larger.
+///
+/// @param Map    { Space[] -> Scatter[] }
+/// @param Strict True for strictly lexicographically larger elements (exclude
+///               same timepoints from the result).
+///
+/// @return { Space[] -> Scatter[] }
+///         A map to all timepoints that happen after the timepoints the input
+///         map originally mapped to.
+IslPtr<isl_map> afterScatter(IslPtr<isl_map> Map, bool Strict);
+
+/// Piecewise afterScatter(IslPtr<isl_map>,bool).
+IslPtr<isl_union_map> afterScatter(NonowningIslPtr<isl_union_map> UMap,
+                                   bool Strict);
+
+/// Construct a range of timepoints between two timepoints.
+///
+/// Example:
+/// From := { A[] -> [0]; B[] -> [0] }
+/// To   := {             B[] -> [10]; C[] -> [20] }
+///
+/// Result:
+/// { B[] -> [i] : 0 < i < 10 }
+///
+/// Note that A[] and C[] are not in the result because they do not have a start
+/// or end timepoint. If a start (or end) timepoint is not unique, the first
+/// (respectively last) is chosen.
+///
+/// @param From     { Space[] -> Scatter[] }
+///                 Map to start timepoints.
+/// @param To       { Space[] -> Scatter[] }
+///                 Map to end timepoints.
+/// @param InclFrom Whether to include the start timepoints in the result. In
+///                 the example, this would add { B[] -> [0] }
+/// @param InclTo   Whether to include the end timepoints in the result. In this
+///                 example, this would add { B[] -> [10] }
+///
+/// @return { Space[] -> Scatter[] }
+///         A map for each domain element of timepoints between two extreme
+///         points, or nullptr if @p From or @p To is nullptr, or the isl max
+///         operations is exceeded.
+IslPtr<isl_map> betweenScatter(IslPtr<isl_map> From, IslPtr<isl_map> To,
+                               bool InclFrom, bool InclTo);
+
+/// Piecewise betweenScatter(IslPtr<isl_map>,IslPtr<isl_map>,bool,bool).
+IslPtr<isl_union_map> betweenScatter(IslPtr<isl_union_map> From,
+                                     IslPtr<isl_union_map> To, bool InclFrom,
+                                     bool InclTo);
+
+/// If by construction a union map is known to contain only a single map, return
+/// it.
+///
+/// This function combines isl_map_from_union_map() and
+/// isl_union_map_extract_map(). isl_map_from_union_map() fails if the map is
+/// empty because it does not know which space it would be in.
+/// isl_union_map_extract_map() on the other hand does not check whether there
+/// is (at most) one isl_map in the union, i.e. how it has been constructed is
+/// probably wrong.
+IslPtr<isl_map> singleton(IslPtr<isl_union_map> UMap,
+                          IslPtr<isl_space> ExpectedSpace);
+
+/// If by construction an isl_union_set is known to contain only a single
+/// isl_set, return it.
+///
+/// This function combines isl_set_from_union_set() and
+/// isl_union_set_extract_set(). isl_map_from_union_set() fails if the set is
+/// empty because it does not know which space it would be in.
+/// isl_union_set_extract_set() on the other hand does not check whether there
+/// is (at most) one isl_set in the union, i.e. how it has been constructed is
+/// probably wrong.
+IslPtr<isl_set> singleton(IslPtr<isl_union_set> USet,
+                          IslPtr<isl_space> ExpectedSpace);
+
+/// Determine how many dimensions the scatter space of @p Schedule has.
+///
+/// The schedule must not be empty and have equal number of dimensions of any
+/// subspace it contains.
+///
+/// The implementation currently returns the maximum number of dimensions it
+/// encounters, if different, and 0 if none is encountered. However, most other
+/// code will most likely fail if one of these happen.
+unsigned getNumScatterDims(NonowningIslPtr<isl_union_map> Schedule);
+
+/// Return the scatter space of a @p Schedule.
+///
+/// This is basically the range space of the schedule map, but harder to
+/// determine because it is an isl_union_map.
+IslPtr<isl_space> getScatterSpace(NonowningIslPtr<isl_union_map> Schedule);
+
+/// Construct an identity map for the given domain values.
+///
+/// There is no type resembling isl_union_space, hence we have to pass an
+/// isl_union_set as the map's domain and range space.
+///
+/// @param USet           { Space[] }
+///                       The returned map's domain and range.
+/// @param RestrictDomain If true, the returned map only maps elements contained
+///                       in @p USet and no other. If false, it returns an
+///                       overapproximation with the identity maps of any space
+///                       in @p USet, not just the elements in it.
+///
+/// @return { Space[] -> Space[] }
+///         A map that maps each value of @p USet to itself.
+IslPtr<isl_union_map> makeIdentityMap(NonowningIslPtr<isl_union_set> USet,
+                                      bool RestrictDomain);
+
+/// Reverse the nested map tuple in @p Map's domain.
+///
+/// @param Map { [Space1[] -> Space2[]] -> Space3[] }
+///
+/// @return { [Space2[] -> Space1[]] -> Space3[] }
+IslPtr<isl_map> reverseDomain(IslPtr<isl_map> Map);
+
+/// Piecewise reverseDomain(IslPtr<isl_map>).
+IslPtr<isl_union_map> reverseDomain(NonowningIslPtr<isl_union_map> UMap);
+
+/// Add a constant to one dimension of a set.
+///
+/// @param Map    The set to shift a dimension in.
+/// @param Pos    The dimension to shift. If negative, the dimensions are
+///               counted from the end instead from the beginning. E.g. -1 is
+///               the last dimension in the tuple.
+/// @param Amount The offset to add to the specified dimension.
+///
+/// @return The modified set.
+IslPtr<isl_set> shiftDim(IslPtr<isl_set> Set, int Pos, int Amount);
+
+/// Piecewise shiftDim(IslPtr<isl_set>,int,int).
+IslPtr<isl_union_set> shiftDim(IslPtr<isl_union_set> USet, int Pos, int Amount);
+
+/// Simplify a set inplace.
+void simplify(IslPtr<isl_set> &Set);
+
+/// Simplify a union set inplace.
+void simplify(IslPtr<isl_union_set> &USet);
+
+/// Simplify a map inplace.
+void simplify(IslPtr<isl_map> &Map);
+
+/// Simplify a union map inplace.
+void simplify(IslPtr<isl_union_map> &UMap);
+
+} // namespace polly
+
+#endif /* POLLY_ISLTOOLS_H */
diff --git a/polly/lib/CMakeLists.txt b/polly/lib/CMakeLists.txt
index c4ae26f9f44..673db5638ad 100644
--- a/polly/lib/CMakeLists.txt
+++ b/polly/lib/CMakeLists.txt
@@ -50,6 +50,7 @@ add_polly_library(Polly
   Support/RegisterPasses.cpp
   Support/ScopHelper.cpp
   Support/ScopLocation.cpp
+  Support/ISLTools.cpp
   ${POLLY_JSON_FILES}
   Transform/Canonicalization.cpp
   Transform/CodePreparation.cpp
diff --git a/polly/lib/Support/ISLTools.cpp b/polly/lib/Support/ISLTools.cpp
new file mode 100644
index 00000000000..9889faf2735
--- /dev/null
+++ b/polly/lib/Support/ISLTools.cpp
@@ -0,0 +1,264 @@
+//===------ ISLTools.cpp ----------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Tools, utilities, helpers and extensions useful in conjunction with the
+// Integer Set Library (isl).
+//
+//===----------------------------------------------------------------------===//
+
+#include "polly/Support/ISLTools.h"
+
+using namespace polly;
+
+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.
+IslPtr<isl_multi_aff> makeShiftDimAff(IslPtr<isl_space> Space, int Pos,
+                                      int Amount) {
+  auto Identity = give(isl_multi_aff_identity(Space.take()));
+  if (Amount == 0)
+    return Identity;
+  auto ShiftAff = give(isl_multi_aff_get_aff(Identity.keep(), Pos));
+  ShiftAff = give(isl_aff_set_constant_si(ShiftAff.take(), Amount));
+  return give(isl_multi_aff_set_aff(Identity.take(), Pos, ShiftAff.take()));
+}
+
+/// Construct a map that swaps two nested tuples.
+///
+/// @param FromSpace1 { Space1[] }
+/// @param FromSpace2 { Space2[] }
+///
+/// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
+IslPtr<isl_basic_map> makeTupleSwapBasicMap(IslPtr<isl_space> FromSpace1,
+                                            IslPtr<isl_space> FromSpace2) {
+  assert(isl_space_is_set(FromSpace1.keep()) != isl_bool_false);
+  assert(isl_space_is_set(FromSpace2.keep()) != isl_bool_false);
+
+  auto Dims1 = isl_space_dim(FromSpace1.keep(), isl_dim_set);
+  auto Dims2 = isl_space_dim(FromSpace2.keep(), isl_dim_set);
+  auto FromSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
+      FromSpace1.copy(), FromSpace2.copy())));
+  auto ToSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
+      FromSpace2.take(), FromSpace1.take())));
+  auto MapSpace = give(
+      isl_space_map_from_domain_and_range(FromSpace.take(), ToSpace.take()));
+
+  auto Result = give(isl_basic_map_universe(MapSpace.take()));
+  for (auto i = Dims1 - Dims1; i < Dims1; i += 1) {
+    Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, i,
+                                       isl_dim_out, Dims2 + i));
+  }
+  for (auto i = Dims2 - Dims2; i < Dims2; i += 1) {
+    Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, Dims1 + i,
+                                       isl_dim_out, i));
+  }
+
+  return Result;
+}
+
+/// Like makeTupleSwapBasicMap(IslPtr<isl_space>,IslPtr<isl_space>), but returns
+/// an isl_map.
+IslPtr<isl_map> makeTupleSwapMap(IslPtr<isl_space> FromSpace1,
+                                 IslPtr<isl_space> FromSpace2) {
+  auto BMapResult =
+      makeTupleSwapBasicMap(std::move(FromSpace1), std::move(FromSpace2));
+  return give(isl_map_from_basic_map(BMapResult.take()));
+}
+} // anonymous namespace
+
+IslPtr<isl_map> polly::beforeScatter(IslPtr<isl_map> Map, bool Strict) {
+  auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
+  auto ScatterRel = give(Strict ? isl_map_lex_gt(RangeSpace.take())
+                                : isl_map_lex_ge(RangeSpace.take()));
+  return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
+}
+
+IslPtr<isl_union_map> polly::beforeScatter(IslPtr<isl_union_map> UMap,
+                                           bool Strict) {
+  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
+  foreachElt(UMap, [=, &Result](IslPtr<isl_map> Map) {
+    auto After = beforeScatter(Map, Strict);
+    Result = give(isl_union_map_add_map(Result.take(), After.take()));
+  });
+  return Result;
+}
+
+IslPtr<isl_map> polly::afterScatter(IslPtr<isl_map> Map, bool Strict) {
+  auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
+  auto ScatterRel = give(Strict ? isl_map_lex_lt(RangeSpace.take())
+                                : isl_map_lex_le(RangeSpace.take()));
+  return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
+}
+
+IslPtr<isl_union_map> polly::afterScatter(NonowningIslPtr<isl_union_map> UMap,
+                                          bool Strict) {
+  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
+  foreachElt(UMap, [=, &Result](IslPtr<isl_map> Map) {
+    auto After = afterScatter(Map, Strict);
+    Result = give(isl_union_map_add_map(Result.take(), After.take()));
+  });
+  return Result;
+}
+
+IslPtr<isl_map> polly::betweenScatter(IslPtr<isl_map> From, IslPtr<isl_map> To,
+                                      bool InclFrom, bool InclTo) {
+  auto AfterFrom = afterScatter(From, !InclFrom);
+  auto BeforeTo = beforeScatter(To, !InclTo);
+
+  return give(isl_map_intersect(AfterFrom.take(), BeforeTo.take()));
+}
+
+IslPtr<isl_union_map> polly::betweenScatter(IslPtr<isl_union_map> From,
+                                            IslPtr<isl_union_map> To,
+                                            bool InclFrom, bool InclTo) {
+  auto AfterFrom = afterScatter(From, !InclFrom);
+  auto BeforeTo = beforeScatter(To, !InclTo);
+
+  return give(isl_union_map_intersect(AfterFrom.take(), BeforeTo.take()));
+}
+
+IslPtr<isl_map> polly::singleton(IslPtr<isl_union_map> UMap,
+                                 IslPtr<isl_space> ExpectedSpace) {
+  if (!UMap)
+    return nullptr;
+
+  if (isl_union_map_n_map(UMap.keep()) == 0)
+    return give(isl_map_empty(ExpectedSpace.take()));
+
+  auto Result = give(isl_map_from_union_map(UMap.take()));
+  assert(
+      !Result ||
+      isl_space_has_equal_tuples(give(isl_map_get_space(Result.keep())).keep(),
+                                 ExpectedSpace.keep()) == isl_bool_true);
+  return Result;
+}
+
+IslPtr<isl_set> polly::singleton(IslPtr<isl_union_set> USet,
+                                 IslPtr<isl_space> ExpectedSpace) {
+  if (!USet)
+    return nullptr;
+
+  if (isl_union_set_n_set(USet.keep()) == 0)
+    return give(isl_set_empty(ExpectedSpace.copy()));
+
+  auto Result = give(isl_set_from_union_set(USet.take()));
+  assert(
+      !Result ||
+      isl_space_has_equal_tuples(give(isl_set_get_space(Result.keep())).keep(),
+                                 ExpectedSpace.keep()) == isl_bool_true);
+  return Result;
+}
+
+unsigned polly::getNumScatterDims(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;
+}
+
+IslPtr<isl_space>
+polly::getScatterSpace(NonowningIslPtr<isl_union_map> Schedule) {
+  if (!Schedule)
+    return nullptr;
+  auto Dims = getNumScatterDims(Schedule);
+  auto ScatterSpace =
+      give(isl_space_set_from_params(isl_union_map_get_space(Schedule.keep())));
+  return give(isl_space_add_dims(ScatterSpace.take(), isl_dim_set, Dims));
+}
+
+IslPtr<isl_union_map>
+polly::makeIdentityMap(NonowningIslPtr<isl_union_set> USet,
+                       bool RestrictDomain) {
+  auto Result = give(isl_union_map_empty(isl_union_set_get_space(USet.keep())));
+  foreachElt(USet, [=, &Result](IslPtr<isl_set> Set) {
+    auto IdentityMap = give(isl_map_identity(
+        isl_space_map_from_set(isl_set_get_space(Set.keep()))));
+    if (RestrictDomain)
+      IdentityMap =
+          give(isl_map_intersect_domain(IdentityMap.take(), Set.take()));
+    Result = give(isl_union_map_add_map(Result.take(), IdentityMap.take()));
+  });
+  return Result;
+}
+
+IslPtr<isl_map> polly::reverseDomain(IslPtr<isl_map> Map) {
+  auto DomSpace =
+      give(isl_space_unwrap(isl_space_domain(isl_map_get_space(Map.keep()))));
+  auto Space1 = give(isl_space_domain(DomSpace.copy()));
+  auto Space2 = give(isl_space_range(DomSpace.take()));
+  auto Swap = makeTupleSwapMap(std::move(Space1), std::move(Space2));
+  return give(isl_map_apply_domain(Map.take(), Swap.take()));
+}
+
+IslPtr<isl_union_map>
+polly::reverseDomain(NonowningIslPtr<isl_union_map> UMap) {
+  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
+  foreachElt(UMap, [=, &Result](IslPtr<isl_map> Map) {
+    auto Reversed = reverseDomain(std::move(Map));
+    Result = give(isl_union_map_add_map(Result.take(), Reversed.take()));
+  });
+  return Result;
+}
+
+IslPtr<isl_set> polly::shiftDim(IslPtr<isl_set> Set, int Pos, int Amount) {
+  int NumDims = isl_set_dim(Set.keep(), isl_dim_set);
+  if (Pos < 0)
+    Pos = NumDims + Pos;
+  assert(Pos < NumDims && "Dimension index must be in range");
+  auto Space = give(isl_set_get_space(Set.keep()));
+  Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
+  auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
+  auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
+  return give(isl_set_apply(Set.take(), TranslatorMap.take()));
+}
+
+IslPtr<isl_union_set> polly::shiftDim(IslPtr<isl_union_set> USet, int Pos,
+                                      int Amount) {
+  auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
+  foreachElt(USet, [=, &Result](IslPtr<isl_set> Set) {
+    auto Shifted = shiftDim(Set, Pos, Amount);
+    Result = give(isl_union_set_add_set(Result.take(), Shifted.take()));
+  });
+  return Result;
+}
+
+void polly::simplify(IslPtr<isl_set> &Set) {
+  Set = give(isl_set_compute_divs(Set.take()));
+  Set = give(isl_set_detect_equalities(Set.take()));
+  Set = give(isl_set_coalesce(Set.take()));
+}
+
+void polly::simplify(IslPtr<isl_union_set> &USet) {
+  USet = give(isl_union_set_compute_divs(USet.take()));
+  USet = give(isl_union_set_detect_equalities(USet.take()));
+  USet = give(isl_union_set_coalesce(USet.take()));
+}
+
+void polly::simplify(IslPtr<isl_map> &Map) {
+  Map = give(isl_map_compute_divs(Map.take()));
+  Map = give(isl_map_detect_equalities(Map.take()));
+  Map = give(isl_map_coalesce(Map.take()));
+}
+
+void polly::simplify(IslPtr<isl_union_map> &UMap) {
+  UMap = give(isl_union_map_compute_divs(UMap.take()));
+  UMap = give(isl_union_map_detect_equalities(UMap.take()));
+  UMap = give(isl_union_map_coalesce(UMap.take()));
+}
diff --git a/polly/unittests/Isl/IslTest.cpp b/polly/unittests/Isl/IslTest.cpp
index c3ef5ba3458..c55f4fb740f 100644
--- a/polly/unittests/Isl/IslTest.cpp
+++ b/polly/unittests/Isl/IslTest.cpp
@@ -8,12 +8,71 @@
 //===----------------------------------------------------------------------===//
 
 #include "polly/Support/GICHelper.h"
+#include "polly/Support/ISLTools.h"
 #include "gtest/gtest.h"
+#include "isl/stream.h"
 #include "isl/val.h"
 
 using namespace llvm;
 using namespace polly;
 
+static IslPtr<isl_space> parseSpace(isl_ctx *Ctx, const char *Str) {
+  isl_stream *Stream = isl_stream_new_str(Ctx, Str);
+  auto Obj = isl_stream_read_obj(Stream);
+
+  IslPtr<isl_space> Result;
+  if (Obj.type == isl_obj_set)
+    Result = give(isl_set_get_space(static_cast<isl_set *>(Obj.v)));
+  else if (Obj.type == isl_obj_map)
+    Result = give(isl_map_get_space(static_cast<isl_map *>(Obj.v)));
+
+  isl_stream_free(Stream);
+  if (Obj.type)
+    Obj.type->free(Obj.v);
+  return Result;
+}
+
+#define SPACE(Str) parseSpace(Ctx.get(), Str)
+
+#define SET(Str) give(isl_set_read_from_str(Ctx.get(), Str))
+#define MAP(Str) give(isl_map_read_from_str(Ctx.get(), Str))
+
+#define USET(Str) give(isl_union_set_read_from_str(Ctx.get(), Str))
+#define UMAP(Str) give(isl_union_map_read_from_str(Ctx.get(), Str))
+
+static bool operator==(const IslPtr<isl_space> &LHS,
+                       const IslPtr<isl_space> &RHS) {
+  auto IsEqual = isl_space_is_equal(LHS.keep(), RHS.keep());
+  EXPECT_NE(isl_bool_error, IsEqual);
+  return IsEqual;
+}
+
+static bool operator==(const IslPtr<isl_set> &LHS, const IslPtr<isl_set> &RHS) {
+  auto IsEqual = isl_set_is_equal(LHS.keep(), RHS.keep());
+  EXPECT_NE(isl_bool_error, IsEqual);
+  return IsEqual;
+}
+
+static bool operator==(const IslPtr<isl_map> &LHS, const IslPtr<isl_map> &RHS) {
+  auto IsEqual = isl_map_is_equal(LHS.keep(), RHS.keep());
+  EXPECT_NE(isl_bool_error, IsEqual);
+  return IsEqual;
+}
+
+static bool operator==(const IslPtr<isl_union_set> &LHS,
+                       const IslPtr<isl_union_set> &RHS) {
+  auto IsEqual = isl_union_set_is_equal(LHS.keep(), RHS.keep());
+  EXPECT_NE(isl_bool_error, IsEqual);
+  return IsEqual;
+}
+
+static bool operator==(const IslPtr<isl_union_map> &LHS,
+                       const IslPtr<isl_union_map> &RHS) {
+  auto IsEqual = isl_union_map_is_equal(LHS.keep(), RHS.keep());
+  EXPECT_NE(isl_bool_error, IsEqual);
+  return IsEqual;
+}
+
 namespace {
 
 TEST(Isl, APIntToIslVal) {
@@ -342,4 +401,241 @@ TEST(Isl, Foreach) {
   }
 }
 
+TEST(ISLTools, beforeScatter) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage with isl_map
+  EXPECT_EQ(MAP("{ [] -> [i] : i <= 0 }"),
+            beforeScatter(MAP("{ [] -> [0] }"), false));
+  EXPECT_EQ(MAP("{ [] -> [i] : i < 0 }"),
+            beforeScatter(MAP("{ [] -> [0] }"), true));
+
+  // Basic usage with isl_union_map
+  EXPECT_EQ(UMAP("{ A[] -> [i] : i <= 0; B[] -> [i] : i <= 0 }"),
+            beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));
+  EXPECT_EQ(UMAP("{ A[] -> [i] : i < 0; B[] -> [i] : i < 0 }"),
+            beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));
+
+  // More than one dimension
+  EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0;  [] -> [i, j] : i = 0 and j <= 0 }"),
+            beforeScatter(UMAP("{ [] -> [0, 0] }"), false));
+  EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0;  [] -> [i, j] : i = 0 and j < 0 }"),
+            beforeScatter(UMAP("{ [] -> [0, 0] }"), true));
+
+  // Functional
+  EXPECT_EQ(UMAP("{ [i] -> [j] : j <= i }"),
+            beforeScatter(UMAP("{ [i] -> [i] }"), false));
+  EXPECT_EQ(UMAP("{ [i] -> [j] : j < i }"),
+            beforeScatter(UMAP("{ [i] -> [i] }"), true));
+
+  // Parametrized
+  EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j <= i }"),
+            beforeScatter(UMAP("[i] -> { [] -> [i] }"), false));
+  EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j < i }"),
+            beforeScatter(UMAP("[i] -> { [] -> [i] }"), true));
+
+  // More than one range
+  EXPECT_EQ(UMAP("{ [] -> [i] : i <= 10 }"),
+            beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));
+  EXPECT_EQ(UMAP("{ [] -> [i] : i < 10 }"),
+            beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));
+
+  // Edge case: empty
+  EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),
+            beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), false));
+  EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),
+            beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), true));
+}
+
+TEST(ISLTools, afterScatter) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage with isl_map
+  EXPECT_EQ(MAP("{ [] -> [i] : i >= 0 }"),
+            afterScatter(MAP("{ [] -> [0] }"), false));
+  EXPECT_EQ(MAP("{ [] -> [i] : i > 0 }"),
+            afterScatter(MAP("{ [] -> [0] }"), true));
+
+  // Basic usage with isl_union_map
+  EXPECT_EQ(UMAP("{ A[] -> [i] : i >= 0; B[] -> [i] : i >= 0 }"),
+            afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));
+  EXPECT_EQ(UMAP("{ A[] -> [i] : i > 0; B[] -> [i] : i > 0 }"),
+            afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));
+
+  // More than one dimension
+  EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0;  [] -> [i, j] : i = 0 and j >= 0 }"),
+            afterScatter(UMAP("{ [] -> [0, 0] }"), false));
+  EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0;  [] -> [i, j] : i = 0 and j > 0 }"),
+            afterScatter(UMAP("{ [] -> [0, 0] }"), true));
+
+  // Functional
+  EXPECT_EQ(UMAP("{ [i] -> [j] : j >= i }"),
+            afterScatter(UMAP("{ [i] -> [i] }"), false));
+  EXPECT_EQ(UMAP("{ [i] -> [j] : j > i }"),
+            afterScatter(UMAP("{ [i] -> [i] }"), true));
+
+  // Parametrized
+  EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j >= i }"),
+            afterScatter(UMAP("[i] -> { [] -> [i] }"), false));
+  EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j > i }"),
+            afterScatter(UMAP("[i] -> { [] -> [i] }"), true));
+
+  // More than one range
+  EXPECT_EQ(UMAP("{ [] -> [i] : i >= 0 }"),
+            afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));
+  EXPECT_EQ(UMAP("{ [] -> [i] : i > 0 }"),
+            afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));
+
+  // Edge case: empty
+  EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), false));
+  EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), true));
+}
+
+TEST(ISLTools, betweenScatter) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage with isl_map
+  EXPECT_EQ(MAP("{ [] -> [i] : 0 < i < 10 }"),
+            betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false,
+                           false));
+  EXPECT_EQ(
+      MAP("{ [] -> [i] : 0 <= i < 10 }"),
+      betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, false));
+  EXPECT_EQ(
+      MAP("{ [] -> [i] : 0 < i <= 10 }"),
+      betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, true));
+  EXPECT_EQ(
+      MAP("{ [] -> [i] : 0 <= i <= 10 }"),
+      betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, true));
+
+  // Basic usage with isl_union_map
+  EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i < 10; B[] -> [i] : 0 < i < 10 }"),
+            betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
+                           UMAP("{ A[] -> [10]; B[] -> [10] }"), false, false));
+  EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i < 10; B[] -> [i] : 0 <= i < 10 }"),
+            betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
+                           UMAP("{ A[] -> [10]; B[] -> [10] }"), true, false));
+  EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i <= 10; B[] -> [i] : 0 < i <= 10 }"),
+            betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
+                           UMAP("{ A[] -> [10]; B[] -> [10] }"), false, true));
+  EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i <= 10; B[] -> [i] : 0 <= i <= 10 }"),
+            betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
+                           UMAP("{ A[] -> [10]; B[] -> [10] }"), true, true));
+}
+
+TEST(ISLTools, singleton) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // No element found
+  EXPECT_EQ(SET("{ [] : 1 = 0 }"), singleton(USET("{ }"), SPACE("{ [] }")));
+  EXPECT_EQ(MAP("{ [] -> [] : 1 = 0  }"),
+            singleton(UMAP("{  }"), SPACE("{ [] -> [] }")));
+
+  // One element found
+  EXPECT_EQ(SET("{ [] }"), singleton(USET("{ [] }"), SPACE("{ [] }")));
+  EXPECT_EQ(MAP("{ [] -> [] }"),
+            singleton(UMAP("{ [] -> [] }"), SPACE("{ [] -> [] }")));
+
+  // Many elements found
+  EXPECT_EQ(SET("{ [i] : 0 <= i < 10 }"),
+            singleton(USET("{ [i] : 0 <= i < 10 }"), SPACE("{ [i] }")));
+  EXPECT_EQ(
+      MAP("{ [i] -> [i] : 0 <= i < 10 }"),
+      singleton(UMAP("{ [i] -> [i] : 0 <= i < 10 }"), SPACE("{ [i] -> [j] }")));
+
+  // Different parameters
+  EXPECT_EQ(SET("[i] -> { [i] }"),
+            singleton(USET("[i] -> { [i] }"), SPACE("{ [i] }")));
+  EXPECT_EQ(MAP("[i] -> { [i] -> [i] }"),
+            singleton(UMAP("[i] -> { [i] -> [i] }"), SPACE("{ [i] -> [j] }")));
+}
+
+TEST(ISLTools, getNumScatterDims) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage
+  EXPECT_EQ(0u, getNumScatterDims(UMAP("{ [] -> [] }")));
+  EXPECT_EQ(1u, getNumScatterDims(UMAP("{ [] -> [i] }")));
+  EXPECT_EQ(2u, getNumScatterDims(UMAP("{ [] -> [i,j] }")));
+  EXPECT_EQ(3u, getNumScatterDims(UMAP("{ [] -> [i,j,k] }")));
+
+  // Different scatter spaces
+  EXPECT_EQ(0u, getNumScatterDims(UMAP("{ A[] -> []; [] -> []}")));
+  EXPECT_EQ(1u, getNumScatterDims(UMAP("{ A[] -> []; [] -> [i] }")));
+  EXPECT_EQ(2u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j] }")));
+  EXPECT_EQ(3u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));
+}
+
+TEST(ISLTools, getScatterSpace) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage
+  EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ [] -> [] }")));
+  EXPECT_EQ(SPACE("{ [i] }"), getScatterSpace(UMAP("{ [] -> [i] }")));
+  EXPECT_EQ(SPACE("{ [i,j] }"), getScatterSpace(UMAP("{ [] -> [i,j] }")));
+  EXPECT_EQ(SPACE("{ [i,j,k] }"), getScatterSpace(UMAP("{ [] -> [i,j,k] }")));
+
+  // Different scatter spaces
+  EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ A[] -> []; [] -> [] }")));
+  EXPECT_EQ(SPACE("{ [i] }"),
+            getScatterSpace(UMAP("{ A[] -> []; [] -> [i] }")));
+  EXPECT_EQ(SPACE("{ [i,j] }"),
+            getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j] }")));
+  EXPECT_EQ(SPACE("{ [i,j,k] }"),
+            getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));
+}
+
+TEST(ISLTools, makeIdentityMap) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage
+  EXPECT_EQ(UMAP("{ [i] -> [i] }"), makeIdentityMap(USET("{ [0] }"), false));
+  EXPECT_EQ(UMAP("{ [0] -> [0] }"), makeIdentityMap(USET("{ [0] }"), true));
+
+  // Multiple spaces
+  EXPECT_EQ(UMAP("{ [] -> []; [i] -> [i] }"),
+            makeIdentityMap(USET("{ []; [0] }"), false));
+  EXPECT_EQ(UMAP("{ [] -> []; [0] -> [0] }"),
+            makeIdentityMap(USET("{ []; [0] }"), true));
+
+  // Edge case: empty
+  EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), false));
+  EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), true));
+}
+
+TEST(ISLTools, reverseDomain) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage
+  EXPECT_EQ(MAP("{ [B[] -> A[]] -> [] }"),
+            reverseDomain(MAP("{ [A[] -> B[]] -> [] }")));
+  EXPECT_EQ(UMAP("{ [B[] -> A[]] -> [] }"),
+            reverseDomain(UMAP("{ [A[] -> B[]] -> [] }")));
+}
+
+TEST(ISLTools, shiftDim) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
+                                                        &isl_ctx_free);
+
+  // Basic usage
+  EXPECT_EQ(SET("{ [1] }"), shiftDim(SET("{ [0] }"), 0, 1));
+  EXPECT_EQ(USET("{ [1] }"), shiftDim(USET("{ [0] }"), 0, 1));
+
+  // From-end indexing
+  EXPECT_EQ(USET("{ [0,0,1] }"), shiftDim(USET("{ [0,0,0] }"), -1, 1));
+  EXPECT_EQ(USET("{ [0,1,0] }"), shiftDim(USET("{ [0,0,0] }"), -2, 1));
+  EXPECT_EQ(USET("{ [1,0,0] }"), shiftDim(USET("{ [0,0,0] }"), -3, 1));
+
+  // Parametrized
+  EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1));
+}
+
 } // anonymous namespace