[Polly][Ast] Partial refactoring of IslAst and IslAstInfo to use isl++. NFC.

[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 IslAst
  • getAst() getRunCondition() buildRunCondition()
  • Removed the destructor in favor of the default one
• Change the type of the attribute IslAst.RunCondition to isl::ast_expr
• Change the type of the attribute IslAst.Root to isl::ast_node
• Change the order of attributes in class IslAst to reflect the data dependencies so that the destructor won't complain
• Refactoring the following methods of class IslAstInfo
  • getAst() getRunCondition()

[patacca]

There is the question on how we want to access the isl::ast_expr object RunCondition.
Right now I declared RunCondition as type isl::ast_expr so the object lives inside IslAst class. Unfortunately the C++ bindings do not define yet the move constructor nor the move assignment so when doing

RunCondition(std::move(O.RunCondition))
Condition = IslAst::buildRunCondition(*S, Build)

we are relying on compiler optimizations to eliminate the unnecessary copies.
I think there is the idea of implementing move constructor and move assignment in the future for isl bindings so it might be ok to just leave the code like this in the mean time.
Otherwise with a little trick we can do r-value assignment like this:

Condition = isl::manage(O.RunCondition.release())

It feels a bit ugly though.

Another way would be to use unique_ptr<isl::ast_expr> instead of the object itself. That way we do not need isl defined move constructor and move assigment.

[patacca]

Changelog:

• Completing the refactoring of IslAst::buildRunCondition()

[Meinersbur]

It is correct that the addition of move semantics was intended to be done eventually. Thus would be one of the things to do for the GSoC project.

Until then we accepted that without these move semantics, there are redundant calls to *_copy and *_free calls. More critically, it may lead to additional object copies when calling a __isl_take function, but the reference count is not 1 because of the redundant reference. However, these do not seem to be that significant for the overall performance, so while it could be better, we know that it cane be improved with better bindings. For polly::IslAst::RunCondition, there is always another reference to it (by polly::IslAst::RunCondition) so any __isl_take function will always need to make a copy and the only overhead are the additional *_copy and *_free calls.

That is, don't worry about making additional copies for now.

Btw, other functionality is missing from the isl-noexceptions.h bindings as well, such as most callbacks.

[patacca]

Changelog:

• Remove destructor for class IslAst in favor of default one
• Convert IslAst.Root to isl++
• Change the order of attributes in class IslAst to reflect the data dependencies so that the destructor won't complain

If it looks good to a reviewer I think we can now land it

[Meinersbur]

Change the order of attributes in class IslAst to reflect the data dependencies so that the destructor won't complain

Nice observation. Did it crash before changing the order?

Could you move the NFC designation to the end of the title? IMHO [NFC] makes the impression that there is component called "NFC". The component here would be IslAst, which you could add as well.
Such as

[Polly][Ast] Partial refactoring of IslAst and IslAstInfo to use isl++. NFC.

I know that there is not consistent placement of NFC in LLVM commits, just stating my personal preference.

The LLVM coding standard uses auto only in very specific cases. In the past we made liberal use of auto, but when changing a declaration we can use the occasion to bring it to the latest coding standard.No need to update this patch because of this since it is unrelated with what the patch is doing, but something to consider for future patches.

Would you like me to push the patch to main?

polly/include/polly/CodeGen/IslAst.h

40

Removing custom dtors is always nice.

polly/lib/CodeGen/IslAst.cpp

409

The isl-noexceptions.h don't implement move ctors/assignments. so std::move currently has no effect.

Still nice to consider move-semantics for when it finally is supported.

[patacca]

Change the order of attributes in class IslAst to reflect the data dependencies so that the destructor won't complain

Nice observation. Did it crash before changing the order?

Yes, it failed some tests. If I remember correctly it was ending up inside isl_ctx_free() with a reference counter > 0 and thus calling isl_die().

The LLVM coding standard uses auto only in very specific cases. In the past we made liberal use of auto, but when changing a declaration we can use the occasion to bring it to the latest coding standard.No need to update this patch because of this since it is unrelated with what the patch is doing, but something to consider for future patches.

I didn't think too much about it, I will keep it in mind in the future.

Please, go ahead and push it to main.

polly/include/polly/CodeGen/IslAst.h

 struct Dependences;
 
 class IslAst {
 public:
   IslAst(const IslAst &) = delete;
   IslAst &operator=(const IslAst &) = delete;
   IslAst(IslAst &&);
   IslAst &operator=(IslAst &&) = delete;
   ~IslAst();
 
   static IslAst create(Scop &Scop, const Dependences &D);
 
   /// Print a source code representation of the program.
   void pprint(raw_ostream &OS);
 
-  __isl_give isl_ast_node *getAst();
+  isl::ast_node getAst();
 
   const std::shared_ptr<isl_ctx> getSharedIslCtx() const { return Ctx; }
 
   /// Get the run-time conditions for the Scop.
-  __isl_give isl_ast_expr *getRunCondition();
+  isl::ast_expr getRunCondition();
 
   /// Build run-time condition for scop.
   ///
   /// @param S     The scop to build the condition for.
   /// @param Build The isl_build object to use to build the condition.
   ///
   /// @returns An ast expression that describes the necessary run-time check.
-  static isl_ast_expr *buildRunCondition(Scop &S,
-                                         __isl_keep isl_ast_build *Build);
+  static isl::ast_expr buildRunCondition(Scop &S, const isl::ast_build &Build);
 
 private:
   Scop &S;
   isl_ast_node *Root = nullptr;
-  isl_ast_expr *RunCondition = nullptr;
   std::shared_ptr<isl_ctx> Ctx;
+  isl::ast_expr RunCondition;
 
   IslAst(Scop &Scop);
 
   void init(const Dependences &D);
 };
 
 class IslAstInfo {
 public:

 
 public:
   IslAstInfo(Scop &S, const Dependences &D) : S(S), Ast(IslAst::create(S, D)) {}
 
   /// Return the isl AST computed by this IslAstInfo.
   IslAst &getIslAst() { return Ast; }
 
   /// Return a copy of the AST root node.
-  __isl_give isl_ast_node *getAst();
+  isl::ast_node getAst();
 
   /// Get the run condition.
   ///
   /// Only if the run condition evaluates at run-time to a non-zero value, the
   /// assumptions that have been taken hold. If the run condition evaluates to
   /// zero/false some assumptions do not hold and the original code needs to
   /// be executed.
-  __isl_give isl_ast_expr *getRunCondition();
+  isl::ast_expr getRunCondition();
 
   void print(raw_ostream &O);
 
   /// @name Extract information attached to an isl ast (for) node.
   ///
   ///{
   /// Get the complete payload attached to @p Node.
   static IslAstUserPayload *getNodePayload(const isl::ast_node &Node);

polly/lib/CodeGen/CodeGeneration.cpp

static bool CodeGen(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT,
   // DependenceInfo or IslAstInfo around.
   IslAst &Ast = AI.getIslAst();
   if (Ast.getSharedIslCtx() != S.getSharedIslCtx()) {
     LLVM_DEBUG(dbgs() << "Got an IstAst for a different Scop/isl_ctx\n");
     return false;
   }
 
   // Check if we created an isl_ast root node, otherwise exit.
-  isl_ast_node *AstRoot = Ast.getAst();
-  if (!AstRoot)
+  isl::ast_node AstRoot = Ast.getAst();
+  if (AstRoot.is_null())
     return false;
 
   // Collect statistics. Do it before we modify the IR to avoid having it any
   // influence on the result.
   auto ScopStats = S.getStatistics();
   ScopsProcessed++;
 
   auto &DL = S.getFunction().getParent()->getDataLayout();
if (!NodeBuilder.preloadInvariantLoads()) {
     auto *MergeBlock = ExitingBlock->getUniqueSuccessor();
     assert(MergeBlock);
     markBlockUnreachable(*StartBlock, Builder);
     markBlockUnreachable(*ExitingBlock, Builder);
     auto *ExitingBB = S.getExitingBlock();
     assert(ExitingBB);
     DT.changeImmediateDominator(MergeBlock, ExitingBB);
     DT.eraseNode(ExitingBlock);
-
-    isl_ast_node_free(AstRoot);
   } else {
     NodeBuilder.addParameters(S.getContext().release());
-    Value *RTC = NodeBuilder.createRTC(AI.getRunCondition());
+    Value *RTC = NodeBuilder.createRTC(AI.getRunCondition().release());
 
     Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
 
     // Explicitly set the insert point to the end of the block to avoid that a
     // split at the builder's current
     // insert position would move the malloc calls to the wrong BasicBlock.
     // Ideally we would just split the block during allocation of the new
     // arrays, but this would break the assumption that there are no blocks
     // between polly.start and polly.exiting (at this point).
     Builder.SetInsertPoint(StartBlock->getTerminator());
 
-    NodeBuilder.create(AstRoot);
+    NodeBuilder.create(AstRoot.release());
     NodeBuilder.finalize();
     fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);
 
     CodegenedScops++;
     CodegenedAffineLoops += ScopStats.NumAffineLoops;
     CodegenedBoxedLoops += ScopStats.NumBoxedLoops;
   }
 

polly/lib/CodeGen/IslAst.cpp

static isl::ast_expr buildCondition(Scop &S, isl::ast_build Build,
   }
 
   if (NonAliasGroup.is_null())
     NonAliasGroup = True;
 
   return NonAliasGroup;
 }
 
-__isl_give isl_ast_expr *
-IslAst::buildRunCondition(Scop &S, __isl_keep isl_ast_build *Build) {
-  isl_ast_expr *RunCondition;
+isl::ast_expr IslAst::buildRunCondition(Scop &S, const isl::ast_build &Build) {
+  isl::ast_expr RunCondition;
 
   // The conditions that need to be checked at run-time for this scop are
   // available as an isl_set in the runtime check context from which we can
   // directly derive a run-time condition.
-  auto *PosCond =
-      isl_ast_build_expr_from_set(Build, S.getAssumedContext().release());
+  auto PosCond = Build.expr_from(S.getAssumedContext());
   if (S.hasTrivialInvalidContext()) {
-    RunCondition = PosCond;
+    RunCondition = std::move(PosCond);
   } else {
-    auto *ZeroV = isl_val_zero(isl_ast_build_get_ctx(Build));
-    auto *NegCond =
-        isl_ast_build_expr_from_set(Build, S.getInvalidContext().release());
-    auto *NotNegCond = isl_ast_expr_eq(isl_ast_expr_from_val(ZeroV), NegCond);
-    RunCondition = isl_ast_expr_and(PosCond, NotNegCond);
+    auto ZeroV = isl::val::zero(Build.get_ctx());
+    auto NegCond = Build.expr_from(S.getInvalidContext());
+    auto NotNegCond =
+        isl::ast_expr::from_val(std::move(ZeroV)).eq(std::move(NegCond));
+    RunCondition =
+        isl::manage(isl_ast_expr_and(PosCond.release(), NotNegCond.release()));
   }
 
   // Create the alias checks from the minimal/maximal accesses in each alias
   // group which consists of read only and non read only (read write) accesses.
   // This operation is by construction quadratic in the read-write pointers and
   // linear in the read only pointers in each alias group.
   for (const Scop::MinMaxVectorPairTy &MinMaxAccessPair : S.getAliasGroups()) {
     auto &MinMaxReadWrite = MinMaxAccessPair.first;
     auto &MinMaxReadOnly = MinMaxAccessPair.second;
     auto RWAccEnd = MinMaxReadWrite.end();
 
     for (auto RWAccIt0 = MinMaxReadWrite.begin(); RWAccIt0 != RWAccEnd;
          ++RWAccIt0) {
       for (auto RWAccIt1 = RWAccIt0 + 1; RWAccIt1 != RWAccEnd; ++RWAccIt1)
-        RunCondition = isl_ast_expr_and(
-            RunCondition,
-            buildCondition(S, isl::manage_copy(Build), RWAccIt0, RWAccIt1)
-                .release());
+        RunCondition = isl::manage(isl_ast_expr_and(
+            RunCondition.release(),
+            buildCondition(S, Build, RWAccIt0, RWAccIt1).release()));
       for (const Scop::MinMaxAccessTy &ROAccIt : MinMaxReadOnly)
-        RunCondition = isl_ast_expr_and(
-            RunCondition,
-            buildCondition(S, isl::manage_copy(Build), RWAccIt0, &ROAccIt)
-                .release());
+        RunCondition = isl::manage(isl_ast_expr_and(
+            RunCondition.release(),
+            buildCondition(S, Build, RWAccIt0, &ROAccIt).release()));
     }
   }
 
   return RunCondition;
 }
 
 /// Simple cost analysis for a given SCoP.
 ///
isl_ast_node_foreach_descendant_top_down(
         return isl_bool_true;
       },
       nullptr);
 }
 
 IslAst::IslAst(Scop &Scop) : S(Scop), Ctx(Scop.getSharedIslCtx()) {}
 
 IslAst::IslAst(IslAst &&O)
-    : S(O.S), Root(O.Root), RunCondition(O.RunCondition), Ctx(O.Ctx) {
+    : S(O.S), Root(O.Root), Ctx(O.Ctx),
+      RunCondition(std::move(O.RunCondition)) {
   O.Root = nullptr;
-  O.RunCondition = nullptr;
 }
 
-IslAst::~IslAst() {
-  isl_ast_node_free(Root);
-  isl_ast_expr_free(RunCondition);
-}
+IslAst::~IslAst() { isl_ast_node_free(Root); }
 
 void IslAst::init(const Dependences &D) {
   bool PerformParallelTest = PollyParallel || DetectParallel ||
                              PollyVectorizerChoice != VECTORIZER_NONE;
   auto ScheduleTree = S.getScheduleTree();
 
   // Skip AST and code generation if there was no benefit achieved.
   if (!benefitsFromPolly(S, PerformParallelTest))
if (PerformParallelTest) {
 
     Build = isl_ast_build_set_before_each_mark(Build, &astBuildBeforeMark,
                                                &BuildInfo);
 
     Build = isl_ast_build_set_after_each_mark(Build, &astBuildAfterMark,
                                               &BuildInfo);
   }
 
-  RunCondition = buildRunCondition(S, Build);
+  RunCondition = buildRunCondition(S, isl::manage_copy(Build));
 
   Root = isl_ast_build_node_from_schedule(Build, S.getScheduleTree().release());
   walkAstForStatistics(Root);
 
   isl_ast_build_free(Build);
 }
 
 IslAst IslAst::create(Scop &Scop, const Dependences &D) {
   IslAst Ast{Scop};
   Ast.init(D);
   return Ast;
 }
 
-__isl_give isl_ast_node *IslAst::getAst() { return isl_ast_node_copy(Root); }
-__isl_give isl_ast_expr *IslAst::getRunCondition() {
-  return isl_ast_expr_copy(RunCondition);
-}
+isl::ast_node IslAst::getAst() { return isl::manage_copy(Root); }
+isl::ast_expr IslAst::getRunCondition() { return RunCondition; }
 
-__isl_give isl_ast_node *IslAstInfo::getAst() { return Ast.getAst(); }
-__isl_give isl_ast_expr *IslAstInfo::getRunCondition() {
-  return Ast.getRunCondition();
-}
+isl::ast_node IslAstInfo::getAst() { return Ast.getAst(); }
+isl::ast_expr IslAstInfo::getRunCondition() { return Ast.getRunCondition(); }
 
 IslAstUserPayload *IslAstInfo::getNodePayload(const isl::ast_node &Node) {
   isl::id Id = Node.get_annotation();
   if (!Id)
     return nullptr;
   IslAstUserPayload *Payload = (IslAstUserPayload *)Id.get_user();
   return Payload;
 }
static __isl_give isl_printer *cbPrintUser(__isl_take isl_printer *P,
   P = isl_printer_end_line(P);
 
   isl_ast_print_options_free(O);
   return P;
 }
 
 void IslAstInfo::print(raw_ostream &OS) {
   isl_ast_print_options *Options;
-  isl_ast_node *RootNode = Ast.getAst();
+  isl::ast_node RootNode = Ast.getAst();
   Function &F = S.getFunction();
 
   OS << ":: isl ast :: " << F.getName() << " :: " << S.getNameStr() << "\n";
 
-  if (!RootNode) {
+  if (RootNode.is_null()) {
     OS << ":: isl ast generation and code generation was skipped!\n\n";
     OS << ":: This is either because no useful optimizations could be applied "
           "(use -polly-process-unprofitable to enforce code generation) or "
           "because earlier passes such as dependence analysis timed out (use "
           "-polly-dependences-computeout=0 to set dependence analysis timeout "
           "to infinity)\n\n";
     return;
   }
 
-  isl_ast_expr *RunCondition = Ast.getRunCondition();
+  isl::ast_expr RunCondition = Ast.getRunCondition();
   char *RtCStr, *AstStr;
 
   Options = isl_ast_print_options_alloc(S.getIslCtx().get());
 
   if (PrintAccesses)
     Options =
         isl_ast_print_options_set_print_user(Options, cbPrintUser, nullptr);
   Options = isl_ast_print_options_set_print_for(Options, cbPrintFor, nullptr);
 
   isl_printer *P = isl_printer_to_str(S.getIslCtx().get());
   P = isl_printer_set_output_format(P, ISL_FORMAT_C);
-  P = isl_printer_print_ast_expr(P, RunCondition);
+  P = isl_printer_print_ast_expr(P, RunCondition.get());
   RtCStr = isl_printer_get_str(P);
   P = isl_printer_flush(P);
   P = isl_printer_indent(P, 4);
-  P = isl_ast_node_print(RootNode, P, Options);
+  P = isl_ast_node_print(RootNode.get(), P, Options);
   AstStr = isl_printer_get_str(P);
 
   auto *Schedule = S.getScheduleTree().release();
 
   LLVM_DEBUG({
     dbgs() << S.getContextStr() << "\n";
     dbgs() << stringFromIslObj(Schedule);
   });
   OS << "\nif (" << RtCStr << ")\n\n";
   OS << AstStr << "\n";
   OS << "else\n";
   OS << "    {  /* original code */ }\n\n";
 
   free(RtCStr);
   free(AstStr);
 
-  isl_ast_expr_free(RunCondition);
   isl_schedule_free(Schedule);
-  isl_ast_node_free(RootNode);
   isl_printer_free(P);
 }
 
 AnalysisKey IslAstAnalysis::Key;
 PreservedAnalyses IslAstPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
                                          ScopStandardAnalysisResults &SAR,
                                          SPMUpdater &U) {
   auto &Ast = SAM.getResult<IslAstAnalysis>(S, SAR);

polly/lib/CodeGen/PPCGCodeGeneration.cpp

void generateCode(__isl_take isl_ast_node *Root, gpu_prog *Prog) {
     GPUNodeBuilder NodeBuilder(Builder, Annotator, *DL, *LI, *SE, *DT, *S,
                                StartBlock, Prog, Runtime, Architecture);
 
     // TODO: Handle LICM
     auto SplitBlock = StartBlock->getSinglePredecessor();
     Builder.SetInsertPoint(SplitBlock->getTerminator());
 
     isl_ast_build *Build = isl_ast_build_alloc(S->getIslCtx().get());
-    isl_ast_expr *Condition = IslAst::buildRunCondition(*S, Build);
+    isl::ast_expr Condition =
+        IslAst::buildRunCondition(*S, isl::manage_copy(Build));
     isl_ast_expr *SufficientCompute = createSufficientComputeCheck(*S, Build);
-    Condition = isl_ast_expr_and(Condition, SufficientCompute);
+    Condition =
+        isl::manage(isl_ast_expr_and(Condition.release(), SufficientCompute));
     isl_ast_build_free(Build);
 
     // preload invariant loads. Note: This should happen before the RTC
     // because the RTC may depend on values that are invariant load hoisted.
     if (!NodeBuilder.preloadInvariantLoads()) {
       // Patch the introduced branch condition to ensure that we always execute
       // the original SCoP.
       auto *FalseI1 = Builder.getFalse();
if (!NodeBuilder.preloadInvariantLoads()) {
       assert(MergeBlock);
       polly::markBlockUnreachable(*StartBlock, Builder);
       polly::markBlockUnreachable(*ExitingBlock, Builder);
       auto *ExitingBB = S->getExitingBlock();
       assert(ExitingBB);
 
       DT->changeImmediateDominator(MergeBlock, ExitingBB);
       DT->eraseNode(ExitingBlock);
-      isl_ast_expr_free(Condition);
       isl_ast_node_free(Root);
     } else {
 
       if (polly::PerfMonitoring) {
         PerfMonitor P(*S, EnteringBB->getParent()->getParent());
         P.initialize();
         P.insertRegionStart(SplitBlock->getTerminator());
 
         // TODO: actually think if this is the correct exiting block to place
         // the `end` performance marker. Invariant load hoisting changes
         // the CFG in a way that I do not precisely understand, so I
         // (Siddharth<[e-mail]>) should come back to this and
         // think about which exiting block to use.
         auto *ExitingBlock = StartBlock->getUniqueSuccessor();
         assert(ExitingBlock);
         BasicBlock *MergeBlock = ExitingBlock->getUniqueSuccessor();
         P.insertRegionEnd(MergeBlock->getTerminator());
       }
 
       NodeBuilder.addParameters(S->getContext().release());
-      Value *RTC = NodeBuilder.createRTC(Condition);
+      Value *RTC = NodeBuilder.createRTC(Condition.release());
       Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
 
       Builder.SetInsertPoint(&*StartBlock->begin());
 
       NodeBuilder.create(Root);
     }
 
     /// In case a sequential kernel has more surrounding loops as any parallel
void getAnalysisUsage(AnalysisUsage &AU) const override {
     // FIXME: We do not yet add regions for the newly generated code to the
     //        region tree.
   }
 };
 } // namespace
 
 char PPCGCodeGeneration::ID = 1;
 
 Pass *polly::createPPCGCodeGenerationPass(GPUArch Arch, GPURuntime Runtime) {
   PPCGCodeGeneration *generator = new PPCGCodeGeneration();
   generator->Runtime = Runtime;
   generator->Architecture = Arch;
   return generator;
 }
 
 INITIALIZE_PASS_BEGIN(PPCGCodeGeneration, "polly-codegen-ppcg",
                       "Polly - Apply PPCG translation to SCOP", false, false)
 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
 INITIALIZE_PASS_END(PPCGCodeGeneration, "polly-codegen-ppcg",
                     "Polly - Apply PPCG translation to SCOP", false, false)