[Polly] [DeadCodeElimination] Translate to C++ bindings

[grosser]

Summary

This pass is a small and self-contained example of a piece of code that was
written with the isl C interface. The diff of this change nicely shows how the
C++ bindings can improve the readability of the code by avoiding the long C
function names and by avoiding any need for memory management.

As you will see, no calls to isl_*_copy or isl_*_free are needed anymore.
Instead the C++ interface takes care of automatically managing the objects.
This may introduce internally additional copies, but due to the isl reference
counting, such copies are expected to be cheap. For performance critical
operations, we will later exploit move semantics to eliminate unnecessary
copies that have shown to be costly.

Below we give a set of examples that shows the benefit of the C++ interface vs.
the pure C interface.

Check properties

Before:

if (isl_aff_is_zero(aff) ||  isl_aff_is_one(aff))
  return true;

After:

if (Aff.isZero() || Aff.isOne())
  return true;

Type conversion

Before:

isl_union_pw_multi_aff *UPMA = isl_union_pw_multi_aff_from_union_map(umap);

After:

isl::UnionPwMultiAff UPMA = UMap;

Type construction

Before:

auto *Empty = isl_union_map_empty(space);

After:

auto Empty = isl::UnionMap::empty(Space);

Operations

Before:

set = isl_union_set_intersect(set, set2);

After:

Set = Set.intersect(Set2);

[Meinersbur]

Looks straightforward

lib/Transform/DeadCodeElimination.cpp

96 ↗

(On Diff #90613)

Will the classes from ScopInfo.h (here: Scop::getSchedule()) be changed eventually as well?

[grosser]

I believe we should move all of Polly to the C++ bindings, but only _after_ they have been agreed on and upstreamed. Before, I would keep this local to the parts that are touched by the changes submitted.

[Meinersbur]

LGTM

lib/Transform/DeadCodeElimination.cpp

141 ↗

(On Diff #90613)

Note that there is a change in behavior here. Before it would enter the condition body on error, now it prints a warning (Which I prefer)

polly/trunk/include/polly/Support/GICHelper.h

 /// @param Ctx      The isl_ctx to create the isl_val in.
 /// @param Int      The integer value to translate.
 /// @param IsSigned If the APInt should be interpreted as signed or unsigned
 ///                 value.
 ///
 /// @return The isl_val corresponding to @p Int.
 __isl_give isl_val *isl_valFromAPInt(isl_ctx *Ctx, const llvm::APInt Int,
                                      bool IsSigned);
+
+/// Translate an llvm::APInt to an isl::val.
+///
+/// Translate the bitsequence without sign information as provided by APInt into
+/// a signed isl::val type. Depending on the value of @p IsSigned @p Int is
+/// interpreted as unsigned value or as signed value in two's complement
+/// representation.
+///
+/// Input IsSigned                 Output
+///
+///     0        0           ->    0
+///     1        0           ->    1
+///    00        0           ->    0
+///    01        0           ->    1
+///    10        0           ->    2
+///    11        0           ->    3
+///
+///     0        1           ->    0
+///     1        1           ->   -1
+///    00        1           ->    0
+///    01        1           ->    1
+///    10        1           ->   -2
+///    11        1           ->   -1
+///
+/// @param Ctx      The isl_ctx to create the isl::val in.
+/// @param Int      The integer value to translate.
+/// @param IsSigned If the APInt should be interpreted as signed or unsigned
+///                 value.
+///
+/// @return The isl::val corresponding to @p Int.
 inline isl::val valFromAPInt(isl_ctx *Ctx, const llvm::APInt Int,
                              bool IsSigned) {
   return isl::manage(isl_valFromAPInt(Ctx, Int, IsSigned));
 }
 
 /// Translate isl_val to llvm::APInt.
 ///
 /// This function can only be called on isl_val values which are integers.

 ///       3 ->    011         3         3
 ///      -4 ->    100        -4         3
 ///       4 ->   0100         4         4
 ///
 /// @param Val The isl val to translate.
 ///
 /// @return The APInt value corresponding to @p Val.
 llvm::APInt APIntFromVal(__isl_take isl_val *Val);
+
+/// Translate isl::val to llvm::APInt.
+///
+/// This function can only be called on isl::val values which are integers.
+/// Calling this function with a non-integral rational, NaN or infinity value
+/// is not allowed.
+///
+/// As the input isl::val may be negative, the APInt that this function returns
+/// must always be interpreted as signed two's complement value. The bitwidth of
+/// the generated APInt is always the minimal bitwidth necessary to model the
+/// provided integer when interpreting the bitpattern as signed value.
+///
+/// Some example conversions are:
+///
+///   Input      Bits    Signed  Bitwidth
+///       0 ->      0         0         1
+///      -1 ->      1        -1         1
+///       1 ->     01         1         2
+///      -2 ->     10        -2         2
+///       2 ->    010         2         3
+///      -3 ->    101        -3         3
+///       3 ->    011         3         3
+///      -4 ->    100        -4         3
+///       4 ->   0100         4         4
+///
+/// @param Val The isl val to translate.
+///
+/// @return The APInt value corresponding to @p Val.
 inline llvm::APInt APIntFromVal(isl::val V) {
   return APIntFromVal(V.release());
 }
 
 /// Get c++ string from Isl objects.
 //@{
 std::string stringFromIslObj(__isl_keep isl_map *map);
 std::string stringFromIslObj(__isl_keep isl_union_map *umap);

polly/trunk/lib/Transform/DeadCodeElimination.cpp

 #include "polly/ScopInfo.h"
 #include "llvm/Support/CommandLine.h"
 #include "isl/flow.h"
 #include "isl/map.h"
 #include "isl/set.h"
 #include "isl/union_map.h"
 #include "isl/union_set.h"
 
+#include "isl-noexceptions.h"
+
 using namespace llvm;
 using namespace polly;
 
 namespace {
 
 cl::opt<int> DCEPreciseSteps(
     "polly-dce-precise-steps",
     cl::desc("The number of precise steps between two approximating "

 private:
   /// Return the set of live iterations.
   ///
   /// The set of live iterations are all iterations that write to memory and for
   /// which we can not prove that there will be a later write that _must_
   /// overwrite the same memory location and is consequently the only one that
   /// is visible after the execution of the SCoP.
   ///
-  isl_union_set *getLiveOut(Scop &S);
+  isl::union_set getLiveOut(Scop &S);
   bool eliminateDeadCode(Scop &S, int PreciseSteps);
 };
 } // namespace
 
 char DeadCodeElim::ID = 0;
 
 // To compute the live outs, we compute for the data-locations that are
 // must-written to the last statement that touches these locations. On top of
 // this we add all statements that perform may-write accesses.
 //
 // We could be more precise by removing may-write accesses for which we know
 // that they are overwritten by a must-write after. However, at the moment the
 // only may-writes we introduce access the full (unbounded) array, such that
 // bounded write accesses can not overwrite all of the data-locations. As
 // this means may-writes are in the current situation always live, there is
 // no point in trying to remove them from the live-out set.
-__isl_give isl_union_set *DeadCodeElim::getLiveOut(Scop &S) {
-  isl_union_map *Schedule = S.getSchedule();
-  assert(Schedule &&
-         "Schedules that contain extension nodes require special handling.");
-  isl_union_map *WriteIterations = isl_union_map_reverse(S.getMustWrites());
-  isl_union_map *WriteTimes =
-      isl_union_map_apply_range(WriteIterations, isl_union_map_copy(Schedule));
-
-  isl_union_map *LastWriteTimes = isl_union_map_lexmax(WriteTimes);
-  isl_union_map *LastWriteIterations = isl_union_map_apply_range(
-      LastWriteTimes, isl_union_map_reverse(Schedule));
-
-  isl_union_set *Live = isl_union_map_range(LastWriteIterations);
-  Live = isl_union_set_union(Live, isl_union_map_domain(S.getMayWrites()));
-  return isl_union_set_coalesce(Live);
+isl::union_set DeadCodeElim::getLiveOut(Scop &S) {
+  isl::union_map Schedule = isl::manage(S.getSchedule());
+  isl::union_map MustWrites = isl::manage(S.getMustWrites());
+  isl::union_map WriteIterations = MustWrites.reverse();
+  isl::union_map WriteTimes = WriteIterations.apply_range(Schedule);
+
+  isl::union_map LastWriteTimes = WriteTimes.lexmax();
+  isl::union_map LastWriteIterations =
+      LastWriteTimes.apply_range(Schedule.reverse());
+
+  isl::union_set Live = LastWriteIterations.range();
+  isl::union_map MayWrites = isl::manage(S.getMayWrites());
+  Live = Live.unite(MayWrites.domain());
+  return Live.coalesce();
 }
 
 /// Performs polyhedral dead iteration elimination by:
 /// o Assuming that the last write to each location is live.
 /// o Following each RAW dependency from a live iteration backwards and adding
 ///   that iteration to the live set.
 ///
 /// To ensure the set of live iterations does not get too complex we always
 /// combine a certain number of precise steps with one approximating step that
 /// simplifies the life set with an affine hull.
 bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
   DependenceInfo &DI = getAnalysis<DependenceInfo>();
   const Dependences &D = DI.getDependences(Dependences::AL_Statement);
 
   if (!D.hasValidDependences())
     return false;
 
-  isl_union_set *Live = getLiveOut(S);
-  isl_union_map *Dep =
-      D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED);
-  Dep = isl_union_map_reverse(Dep);
+  isl::union_set Live = getLiveOut(S);
+  isl::union_map Dep = isl::manage(
+      D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED));
+  Dep = Dep.reverse();
 
   if (PreciseSteps == -1)
-    Live = isl_union_set_affine_hull(Live);
+    Live = Live.affine_hull();
 
-  isl_union_set *OriginalDomain = S.getDomains();
+  isl::union_set OriginalDomain = isl::manage(S.getDomains());
   int Steps = 0;
   while (true) {
-    isl_union_set *Extra;
     Steps++;
 
-    Extra =
-        isl_union_set_apply(isl_union_set_copy(Live), isl_union_map_copy(Dep));
+    isl::union_set Extra = Live.apply(Dep);
 
-    if (isl_union_set_is_subset(Extra, Live)) {
-      isl_union_set_free(Extra);
+    if (Extra.is_subset(Live))
       break;
-    }
 
-    Live = isl_union_set_union(Live, Extra);
+    Live = Live.unite(Extra);
 
     if (Steps > PreciseSteps) {
       Steps = 0;
-      Live = isl_union_set_affine_hull(Live);
+      Live = Live.affine_hull();
     }
 
-    Live = isl_union_set_intersect(Live, isl_union_set_copy(OriginalDomain));
+    Live = Live.intersect(OriginalDomain);
   }
-  isl_union_map_free(Dep);
-  isl_union_set_free(OriginalDomain);
 
-  bool Changed = S.restrictDomains(isl_union_set_coalesce(Live));
+  Live = Live.coalesce();
+
+  bool Changed = S.restrictDomains(Live.copy());
 
   // FIXME: We can probably avoid the recomputation of all dependences by
   // updating them explicitly.
   if (Changed)
     DI.recomputeDependences(Dependences::AL_Statement);
   return Changed;
 }