[Polly][NFC] Partially refactoring of IslAstInfo and IslNodeBuilder to use isl++

[patacca]

Summary

Polly use algorithms from the Integer Set Library (isl), which is a library written in C and which is incompatible with the rest of the LLVM as it is written in C++.

Changes made:

• Refactoring the following methods of class IslAstInfo
  • isParallel() isExecutedInParallel() isReductionParallel() getSchedule() getMinimalDependenceDistance() getBrokenReductions()
• Refactoring the following methods of class IslNodeBuilder
  • getReferencesInSubtree() getScheduleForAstNode()
• Refactoring function getBrokenReductionsStr()
• Fixed the mismatching function declaration for getScheduleForAstNode()

[patacca]

[Polly] Using is_null() from C++ isl bindings

EDIT: This is an erroneous diff. Please ignore it

[patacca]

Using is_null() from isl C++ bindings.
The previous diff was erroneous.

EDIT: This is an erroneous diff. Please ignore it

[patacca]

Using is_null() from isl C++ bindings.

EDIT: This is an erroneous diff. Please ignore it

[patacca]

I had some difficulties with arcanist. This is the right diff.

Changes made:

• Refactoring isParallel() isExecutedInParallel() isReductionParallel() getSchedule() getBrokenReductions() getReferencesInSubtree() getScheduleForAstNode() getBrokenReductionsStr() to take C++ bindings instead of the plain isl C api.
• Fixed the mismatching function declaration for getScheduleForAstNode()
• Using is_null() from isl C++ bindings

[patacca]

Refactoring method getMinimalDependenceDistance()

[Meinersbur]

Thank. Patch itself looks good.

Could you remove the duplicate the repeated title from the summary and append NFC. to the title? (I think I forgot to mention this in the last commit).

Would you like me to push this patch to main?

[patacca]

Changes done.
Please go ahead and push it

polly/include/polly/CodeGen/IslAst.h

public:
   ///{
   /// Get the complete payload attached to @p Node.
   static IslAstUserPayload *getNodePayload(const isl::ast_node &Node);
 
   /// Is this loop an innermost loop?
   static bool isInnermost(const isl::ast_node &Node);
 
   /// Is this loop a parallel loop?
-  static bool isParallel(__isl_keep isl_ast_node *Node);
+  static bool isParallel(const isl::ast_node &Node);
 
   /// Is this loop an outermost parallel loop?
   static bool isOutermostParallel(const isl::ast_node &Node);
 
   /// Is this loop an innermost parallel loop?
   static bool isInnermostParallel(const isl::ast_node &Node);
 
   /// Is this loop a reduction parallel loop?
-  static bool isReductionParallel(__isl_keep isl_ast_node *Node);
+  static bool isReductionParallel(const isl::ast_node &Node);
 
   /// Will the loop be run as thread parallel?
-  static bool isExecutedInParallel(__isl_keep isl_ast_node *Node);
+  static bool isExecutedInParallel(const isl::ast_node &Node);
 
   /// Get the nodes schedule or a nullptr if not available.
-  static __isl_give isl_union_map *getSchedule(__isl_keep isl_ast_node *Node);
+  static isl::union_map getSchedule(const isl::ast_node &Node);
 
   /// Get minimal dependence distance or nullptr if not available.
-  static __isl_give isl_pw_aff *
-  getMinimalDependenceDistance(__isl_keep isl_ast_node *Node);
+  static isl::pw_aff getMinimalDependenceDistance(const isl::ast_node &Node);
 
   /// Get the nodes broken reductions or a nullptr if not available.
-  static MemoryAccessSet *getBrokenReductions(__isl_keep isl_ast_node *Node);
+  static MemoryAccessSet *getBrokenReductions(const isl::ast_node &Node);
 
   /// Get the nodes build context or a nullptr if not available.
   static __isl_give isl_ast_build *getBuild(__isl_keep isl_ast_node *Node);
 
   ///}
 };
 
 struct IslAstAnalysis : public AnalysisInfoMixin<IslAstAnalysis> {

polly/include/polly/CodeGen/IslNodeBuilder.h

protected:
   /// locally defined. Loops that are before the scop, but do not contain the
   /// scop itself are considered not locally defined.
   ///
   /// @param For    The node defining the subtree.
   /// @param Values A vector that will be filled with the Values referenced in
   ///               this subtree.
   /// @param Loops  A vector that will be filled with the Loops referenced in
   ///               this subtree.
-  void getReferencesInSubtree(__isl_keep isl_ast_node *For,
+  void getReferencesInSubtree(const isl::ast_node &For,
                               SetVector<Value *> &Values,
                               SetVector<const Loop *> &Loops);
 
   /// Change the llvm::Value(s) used for code generation.
   ///
   /// When generating code certain values (e.g., references to induction
   /// variables or array base pointers) in the original code may be replaced by
   /// new values. This function allows to (partially) update the set of values
protected:
   /// This information is used to reason about parallelism of loops or the
   /// locality of memory accesses under a given schedule.
   ///
   /// @param Node The node we want to obtain the schedule for.
   /// @return Return an isl_union_map that maps from the statements executed
   ///         below this ast node to the scheduling vectors used to enumerate
   ///         them.
   ///
-  virtual __isl_give isl_union_map *
-  getScheduleForAstNode(__isl_take isl_ast_node *Node);
+  virtual isl::union_map getScheduleForAstNode(const isl::ast_node &Node);
 
 private:
   /// Create code for a copy statement.
   ///
   /// A copy statement is expected to have one read memory access and one write
   /// memory access (in this very order). Data is loaded from the location
   /// described by the read memory access and written to the location described
   /// by the write memory access. @p NewAccesses contains for each access

polly/lib/CodeGen/IslAst.cpp

static isl_printer *printLine(__isl_take isl_printer *Printer,
   Printer = isl_printer_start_line(Printer);
   Printer = isl_printer_print_str(Printer, str.c_str());
   if (PWA)
     Printer = isl_printer_print_pw_aff(Printer, PWA);
   return isl_printer_end_line(Printer);
 }
 
 /// Return all broken reductions as a string of clauses (OpenMP style).
-static const std::string getBrokenReductionsStr(__isl_keep isl_ast_node *Node) {
+static const std::string getBrokenReductionsStr(const isl::ast_node &Node) {
   IslAstInfo::MemoryAccessSet *BrokenReductions;
   std::string str;
 
   BrokenReductions = IslAstInfo::getBrokenReductions(Node);
   if (!BrokenReductions || BrokenReductions->empty())
     return "";
 
   // Map each type of reduction to a comma separated list of the base addresses.
static const std::string getBrokenReductionsStr(const isl::ast_node &Node) {
 
   return str;
 }
 
 /// Callback executed for each for node in the ast in order to print it.
 static isl_printer *cbPrintFor(__isl_take isl_printer *Printer,
                                __isl_take isl_ast_print_options *Options,
                                __isl_keep isl_ast_node *Node, void *) {
-  isl_pw_aff *DD = IslAstInfo::getMinimalDependenceDistance(Node);
-  const std::string BrokenReductionsStr = getBrokenReductionsStr(Node);
+  isl::pw_aff DD =
+      IslAstInfo::getMinimalDependenceDistance(isl::manage_copy(Node));
+  const std::string BrokenReductionsStr =
+      getBrokenReductionsStr(isl::manage_copy(Node));
   const std::string KnownParallelStr = "#pragma known-parallel";
   const std::string DepDisPragmaStr = "#pragma minimal dependence distance: ";
   const std::string SimdPragmaStr = "#pragma simd";
   const std::string OmpPragmaStr = "#pragma omp parallel for";
 
-  if (DD)
-    Printer = printLine(Printer, DepDisPragmaStr, DD);
+  if (!DD.is_null())
+    Printer = printLine(Printer, DepDisPragmaStr, DD.get());
 
   if (IslAstInfo::isInnermostParallel(isl::manage_copy(Node)))
     Printer = printLine(Printer, SimdPragmaStr + BrokenReductionsStr);
 
-  if (IslAstInfo::isExecutedInParallel(Node))
+  if (IslAstInfo::isExecutedInParallel(isl::manage_copy(Node)))
     Printer = printLine(Printer, OmpPragmaStr);
   else if (IslAstInfo::isOutermostParallel(isl::manage_copy(Node)))
     Printer = printLine(Printer, KnownParallelStr + BrokenReductionsStr);
 
-  isl_pw_aff_free(DD);
   return isl_ast_node_for_print(Node, Printer, Options);
 }
 
 /// Check if the current scheduling dimension is parallel.
 ///
 /// In case the dimension is parallel we also check if any reduction
 /// dependences is broken when we exploit this parallelism. If so,
 /// @p IsReductionParallel will be set to true. The reduction dependences we use

 static void walkAstForStatistics(__isl_keep isl_ast_node *Ast) {
   assert(Ast);
   isl_ast_node_foreach_descendant_top_down(
       Ast,
       [](__isl_keep isl_ast_node *Node, void *User) -> isl_bool {
         switch (isl_ast_node_get_type(Node)) {
         case isl_ast_node_for:
           NumForLoops++;
-          if (IslAstInfo::isParallel(Node))
+          if (IslAstInfo::isParallel(isl::manage_copy(Node)))
             NumParallel++;
           if (IslAstInfo::isInnermostParallel(isl::manage_copy(Node)))
             NumInnermostParallel++;
           if (IslAstInfo::isOutermostParallel(isl::manage_copy(Node)))
             NumOutermostParallel++;
-          if (IslAstInfo::isReductionParallel(Node))
+          if (IslAstInfo::isReductionParallel(isl::manage_copy(Node)))
             NumReductionParallel++;
-          if (IslAstInfo::isExecutedInParallel(Node))
+          if (IslAstInfo::isExecutedInParallel(isl::manage_copy(Node)))
             NumExecutedInParallel++;
           break;
 
         case isl_ast_node_if:
           NumIfConditions++;
           break;
 
         default:
IslAstUserPayload *IslAstInfo::getNodePayload(const isl::ast_node &Node) {
   return Payload;
 }
 
 bool IslAstInfo::isInnermost(const isl::ast_node &Node) {
   IslAstUserPayload *Payload = getNodePayload(Node);
   return Payload && Payload->IsInnermost;
 }
 
-bool IslAstInfo::isParallel(__isl_keep isl_ast_node *Node) {
-  return IslAstInfo::isInnermostParallel(isl::manage_copy(Node)) ||
-         IslAstInfo::isOutermostParallel(isl::manage_copy(Node));
+bool IslAstInfo::isParallel(const isl::ast_node &Node) {
+  return IslAstInfo::isInnermostParallel(Node) ||
+         IslAstInfo::isOutermostParallel(Node);
 }
 
 bool IslAstInfo::isInnermostParallel(const isl::ast_node &Node) {
   IslAstUserPayload *Payload = getNodePayload(Node);
   return Payload && Payload->IsInnermostParallel;
 }
 
 bool IslAstInfo::isOutermostParallel(const isl::ast_node &Node) {
   IslAstUserPayload *Payload = getNodePayload(Node);
   return Payload && Payload->IsOutermostParallel;
 }
 
-bool IslAstInfo::isReductionParallel(__isl_keep isl_ast_node *Node) {
-  IslAstUserPayload *Payload = getNodePayload(isl::manage_copy(Node));
+bool IslAstInfo::isReductionParallel(const isl::ast_node &Node) {
+  IslAstUserPayload *Payload = getNodePayload(Node);
   return Payload && Payload->IsReductionParallel;
 }
 
-bool IslAstInfo::isExecutedInParallel(__isl_keep isl_ast_node *Node) {
+bool IslAstInfo::isExecutedInParallel(const isl::ast_node &Node) {
   if (!PollyParallel)
     return false;
 
   // Do not parallelize innermost loops.
   //
   // Parallelizing innermost loops is often not profitable, especially if
   // they have a low number of iterations.
   //
   // TODO: Decide this based on the number of loop iterations that will be
   //       executed. This can possibly require run-time checks, which again
   //       raises the question of both run-time check overhead and code size
   //       costs.
-  if (!PollyParallelForce && isInnermost(isl::manage_copy(Node)))
+  if (!PollyParallelForce && isInnermost(Node))
     return false;
 
-  return isOutermostParallel(isl::manage_copy(Node)) &&
-         !isReductionParallel(Node);
+  return isOutermostParallel(Node) && !isReductionParallel(Node);
 }
 
-__isl_give isl_union_map *
-IslAstInfo::getSchedule(__isl_keep isl_ast_node *Node) {
-  IslAstUserPayload *Payload = getNodePayload(isl::manage_copy(Node));
-  return Payload ? isl_ast_build_get_schedule(Payload->Build) : nullptr;
+isl::union_map IslAstInfo::getSchedule(const isl::ast_node &Node) {
+  IslAstUserPayload *Payload = getNodePayload(Node);
+  if (!Payload)
+    return nullptr;
+
+  isl::ast_build Build = isl::manage_copy(Payload->Build);
+  return Build.get_schedule();
 }
 
-__isl_give isl_pw_aff *
-IslAstInfo::getMinimalDependenceDistance(__isl_keep isl_ast_node *Node) {
-  IslAstUserPayload *Payload = getNodePayload(isl::manage_copy(Node));
-  return Payload ? Payload->MinimalDependenceDistance.copy() : nullptr;
+isl::pw_aff
+IslAstInfo::getMinimalDependenceDistance(const isl::ast_node &Node) {
+  IslAstUserPayload *Payload = getNodePayload(Node);
+  return Payload ? Payload->MinimalDependenceDistance : nullptr;
 }
 
 IslAstInfo::MemoryAccessSet *
-IslAstInfo::getBrokenReductions(__isl_keep isl_ast_node *Node) {
-  IslAstUserPayload *Payload = getNodePayload(isl::manage_copy(Node));
+IslAstInfo::getBrokenReductions(const isl::ast_node &Node) {
+  IslAstUserPayload *Payload = getNodePayload(Node);
   return Payload ? &Payload->BrokenReductions : nullptr;
 }
 
 isl_ast_build *IslAstInfo::getBuild(__isl_keep isl_ast_node *Node) {
   IslAstUserPayload *Payload = getNodePayload(isl::manage_copy(Node));
   return Payload ? Payload->Build : nullptr;
 }
 

polly/lib/CodeGen/IslNodeBuilder.cpp

 static void
 addReferencesFromStmtUnionSet(isl::union_set USet,
                               struct SubtreeReferences &References) {
 
   for (isl::set Set : USet.get_set_list())
     addReferencesFromStmtSet(Set, &References);
 }
 
-__isl_give isl_union_map *
-IslNodeBuilder::getScheduleForAstNode(__isl_keep isl_ast_node *For) {
-  return IslAstInfo::getSchedule(For);
+isl::union_map
+IslNodeBuilder::getScheduleForAstNode(const isl::ast_node &Node) {
+  return IslAstInfo::getSchedule(Node);
 }
 
-void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node *For,
+void IslNodeBuilder::getReferencesInSubtree(const isl::ast_node &For,
                                             SetVector<Value *> &Values,
                                             SetVector<const Loop *> &Loops) {
   SetVector<const SCEV *> SCEVs;
   struct SubtreeReferences References = {
       LI, SE, S, ValueMap, Values, SCEVs, getBlockGenerator(), nullptr};
 
   for (const auto &I : IDToValue)
     Values.insert(I.second);
 
   // NOTE: this is populated in IslNodeBuilder::addParameters
   for (const auto &I : OutsideLoopIterations)
     Values.insert(cast<SCEVUnknown>(I.second)->getValue());
 
-  isl::union_set Schedule =
-      isl::manage(isl_union_map_domain(getScheduleForAstNode(For)));
+  isl::union_set Schedule = getScheduleForAstNode(For).domain();
   addReferencesFromStmtUnionSet(Schedule, References);
 
   for (const SCEV *Expr : SCEVs) {
     findValues(Expr, SE, Values);
     findLoops(Expr, Loops);
   }
 
   Values.remove_if([](const Value *V) { return isa<GlobalValue>(V); });
if (MaxType != ValueInc->getType())
     ValueInc = Builder.CreateSExt(ValueInc, MaxType);
 
   std::vector<Value *> IVS(VectorWidth);
   IVS[0] = ValueLB;
 
   for (int i = 1; i < VectorWidth; i++)
     IVS[i] = Builder.CreateAdd(IVS[i - 1], ValueInc, "p_vector_iv");
 
-  isl_union_map *Schedule = getScheduleForAstNode(For);
-  assert(Schedule && "For statement annotation does not contain its schedule");
+  isl::union_map Schedule = getScheduleForAstNode(isl::manage_copy(For));
+  assert(!Schedule.is_null() &&
+         "For statement annotation does not contain its schedule");
 
   IDToValue[IteratorID] = ValueLB;
 
   switch (isl_ast_node_get_type(Body)) {
   case isl_ast_node_user:
-    createUserVector(Body, IVS, isl_id_copy(IteratorID),
-                     isl_union_map_copy(Schedule));
+    createUserVector(Body, IVS, isl_id_copy(IteratorID), Schedule.copy());
     break;
   case isl_ast_node_block: {
     isl_ast_node_list *List = isl_ast_node_block_get_children(Body);
 
     for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i)
       createUserVector(isl_ast_node_list_get_ast_node(List, i), IVS,
-                       isl_id_copy(IteratorID), isl_union_map_copy(Schedule));
+                       isl_id_copy(IteratorID), Schedule.copy());
 
     isl_ast_node_free(Body);
     isl_ast_node_list_free(List);
     break;
   }
   default:
     isl_ast_node_dump(Body);
     llvm_unreachable("Unhandled isl_ast_node in vectorizer");
   }
 
   IDToValue.erase(IDToValue.find(IteratorID));
   isl_id_free(IteratorID);
-  isl_union_map_free(Schedule);
 
   isl_ast_node_free(For);
   isl_ast_expr_free(Iterator);
 
   VectorLoops++;
 }
 
 /// Restore the initial ordering of dimensions of the band node
void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) {
   if (MaxType != ValueInc->getType())
     ValueInc = Builder.CreateSExt(ValueInc, MaxType);
 
   BasicBlock::iterator LoopBody;
 
   SetVector<Value *> SubtreeValues;
   SetVector<const Loop *> Loops;
 
-  getReferencesInSubtree(For, SubtreeValues, Loops);
+  getReferencesInSubtree(isl::manage_copy(For), SubtreeValues, Loops);
 
   // Create for all loops we depend on values that contain the current loop
   // iteration. These values are necessary to generate code for SCEVs that
   // depend on such loops. As a result we need to pass them to the subfunction.
   // See [Code generation of induction variables of loops outside Scops]
   for (const Loop *L : Loops) {
     Value *LoopInductionVar = materializeNonScopLoopInductionVariable(L);
     SubtreeValues.insert(LoopInductionVar);
return isl_ast_node_foreach_descendant_top_down(
              },
              nullptr) == isl_stat_error;
 }
 
 void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {
   bool Vector = PollyVectorizerChoice == VECTORIZER_POLLY;
 
   if (Vector && IslAstInfo::isInnermostParallel(isl::manage_copy(For)) &&
-      !IslAstInfo::isReductionParallel(For)) {
+      !IslAstInfo::isReductionParallel(isl::manage_copy(For))) {
     int VectorWidth = getNumberOfIterations(isl::manage_copy(For));
     if (1 < VectorWidth && VectorWidth <= 16 && !hasPartialAccesses(For)) {
       createForVector(For, VectorWidth);
       return;
     }
   }
 
-  if (IslAstInfo::isExecutedInParallel(For)) {
+  if (IslAstInfo::isExecutedInParallel(isl::manage_copy(For))) {
     createForParallel(For);
     return;
   }
-  bool Parallel =
-      (IslAstInfo::isParallel(For) && !IslAstInfo::isReductionParallel(For));
+  bool Parallel = (IslAstInfo::isParallel(isl::manage_copy(For)) &&
+                   !IslAstInfo::isReductionParallel(isl::manage_copy(For)));
   createForSequential(isl::manage(For), Parallel);
 }
 
 void IslNodeBuilder::createIf(__isl_take isl_ast_node *If) {
   isl_ast_expr *Cond = isl_ast_node_if_get_cond(If);
 
   Function *F = Builder.GetInsertBlock()->getParent();
   LLVMContext &Context = F->getContext();