1 //===- IslAst.cpp - isl code generator interface --------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
19 // An in-depth discussion of our AST generation approach can be found in:
25 // http://www.grosser.es/#pub-polyhedral-AST-generation
27 //===----------------------------------------------------------------------===//
29 #include "polly/CodeGen/IslAst.h"
30 #include "polly/CodeGen/CodeGeneration.h"
31 #include "polly/DependenceInfo.h"
32 #include "polly/LinkAllPasses.h"
33 #include "polly/Options.h"
34 #include "polly/ScopDetection.h"
35 #include "polly/ScopInfo.h"
36 #include "polly/ScopPass.h"
37 #include "polly/Support/GICHelper.h"
46 #include "isl/isl-noexceptions.h"
55 #include "polly/Support/PollyDebug.h"
56 #define DEBUG_TYPE "polly-ast"
59 using namespace polly;
64     PollyParallel("polly-parallel",
68 static cl::opt<bool> PrintAccesses("polly-ast-print-accesses",
73     "polly-parallel-force",
78 static cl::opt<bool> UseContext("polly-ast-use-context",
82 static cl::opt<bool> DetectParallel("polly-ast-detect-parallel",
91 STATISTIC(NumForLoops, "Number of for-loops");
92 STATISTIC(NumParallel, "Number of parallel for-loops");
93 STATISTIC(NumInnermostParallel, "Number of innermost parallel for-loops");
94 STATISTIC(NumOutermostParallel, "Number of outermost parallel for-loops");
95 STATISTIC(NumReductionParallel, "Number of reduction-parallel for-loops");
96 STATISTIC(NumExecutedInParallel, "Number of for-loops executed in parallel");
97 STATISTIC(NumIfConditions, "Number of if-conditions");
99 namespace polly {  namespace
118 } // namespace polly
142   if (!BrokenReductions || BrokenReductions->empty())  in getBrokenReductionsStr()
148     if (MA->isWrite())  in getBrokenReductionsStr()
149       Clauses[MA->getReductionType()] +=  in getBrokenReductionsStr()
150           ", " + MA->getScopArrayInfo()->getName();  in getBrokenReductionsStr()
172   const std::string KnownParallelStr = "#pragma known-parallel";  in cbPrintFor()
200 /// (or non-zero) dependence distance on the dimension in question.
201 static bool astScheduleDimIsParallel(const isl::ast_build &Build,  in astScheduleDimIsParallel()  argument
204   if (!D->hasValidDependences())  in astScheduleDimIsParallel()
207   isl::union_map Schedule = Build.get_schedule();  in astScheduleDimIsParallel()
208   isl::union_map Dep = D->getDependences(  in astScheduleDimIsParallel()
211   if (!D->isParallel(Schedule.get(), Dep.release())) {  in astScheduleDimIsParallel()
213         D->getDependences(Dependences::TYPE_RAW | Dependences::TYPE_WAW |  in astScheduleDimIsParallel()
217     D->isParallel(Schedule.get(), DepsAll.release(),  in astScheduleDimIsParallel()
219     NodeInfo->MinimalDependenceDistance =  in astScheduleDimIsParallel()
224   isl::union_map RedDeps = D->getDependences(Dependences::TYPE_TC_RED);  in astScheduleDimIsParallel()
225   if (!D->isParallel(Schedule.get(), RedDeps.release()))  in astScheduleDimIsParallel()
226     NodeInfo->IsReductionParallel = true;  in astScheduleDimIsParallel()
228   if (!NodeInfo->IsReductionParallel)  in astScheduleDimIsParallel()
231   for (const auto &MaRedPair : D->getReductionDependences()) {  in astScheduleDimIsParallel()
235     if (!D->isParallel(Schedule.get(), MaRedDeps.release()))  in astScheduleDimIsParallel()
236       NodeInfo->BrokenReductions.insert(MaRedPair.first);  in astScheduleDimIsParallel()
246 // - Detection of openmp parallel loops
248 static __isl_give isl_id *astBuildBeforeFor(__isl_keep isl_ast_build *Build,  in astBuildBeforeFor()  argument
252   isl_id *Id = isl_id_alloc(isl_ast_build_get_ctx(Build), "", Payload);  in astBuildBeforeFor()
254   BuildInfo->LastForNodeId = Id;  in astBuildBeforeFor()
256   Payload->IsParallel = astScheduleDimIsParallel(isl::manage_copy(Build),  in astBuildBeforeFor()
257                                                  BuildInfo->Deps, Payload);  in astBuildBeforeFor()
260   if (!BuildInfo->InParallelFor && !BuildInfo->InSIMD)  in astBuildBeforeFor()
261     BuildInfo->InParallelFor = Payload->IsOutermostParallel =  in astBuildBeforeFor()
262         Payload->IsParallel;  in astBuildBeforeFor()
271 // - Reset the 'InParallelFor' flag, as soon as we leave a for node,
275 astBuildAfterFor(__isl_take isl_ast_node *Node, __isl_keep isl_ast_build *Build,  in astBuildAfterFor()  argument
283   assert(Payload->Build.is_null() && "Build environment already set");  in astBuildAfterFor()
284   Payload->Build = isl::manage_copy(Build);  in astBuildAfterFor()
285   Payload->IsInnermost = (Id == BuildInfo->LastForNodeId);  in astBuildAfterFor()
287   Payload->IsInnermostParallel =  in astBuildAfterFor()
288       Payload->IsInnermost && (BuildInfo->InSIMD || Payload->IsParallel);  in astBuildAfterFor()
289   if (Payload->IsOutermostParallel)  in astBuildAfterFor()
290     BuildInfo->InParallelFor = false;  in astBuildAfterFor()
297                                    __isl_keep isl_ast_build *Build,  in astBuildBeforeMark()  argument
304     BuildInfo->InSIMD = true;  in astBuildBeforeMark()
311                   __isl_keep isl_ast_build *Build, void *User) {  in astBuildAfterMark()  argument
316     BuildInfo->InSIMD = false;  in astBuildAfterMark()
322                                              __isl_keep isl_ast_build *Build,  in AtEachDomain()  argument
327   isl_id *Id = isl_id_alloc(isl_ast_build_get_ctx(Build), "", Payload);  in AtEachDomain()
330   Payload->Build = isl::manage_copy(Build);  in AtEachDomain()
335 // Build alias check condition given a pair of minimal/maximal access.
336 static isl::ast_expr buildCondition(Scop &S, isl::ast_build Build,  in buildCondition()  argument
340   isl::pw_multi_aff AFirst = It0->first;  in buildCondition()
341   isl::pw_multi_aff ASecond = It0->second;  in buildCondition()
342   isl::pw_multi_aff BFirst = It1->first;  in buildCondition()
343   isl::pw_multi_aff BSecond = It1->second;  in buildCondition()
349       isl::ast_expr::from_val(isl::val::int_from_ui(Build.ctx(), 1));  in buildCondition()
351       isl::ast_expr::from_val(isl::val::int_from_ui(Build.ctx(), 0));  in buildCondition()
354       ScopArrayInfo::getFromId(Left)->getBasePtrOriginSAI();  in buildCondition()
356       ScopArrayInfo::getFromId(Right)->getBasePtrOriginSAI();  in buildCondition()
371     MinExpr = Build.access_from(AFirst).address_of();  in buildCondition()
372     MaxExpr = Build.access_from(BSecond).address_of();  in buildCondition()
378     MinExpr = Build.access_from(BFirst).address_of();  in buildCondition()
379     MaxExpr = Build.access_from(ASecond).address_of();  in buildCondition()
395 isl::ast_expr IslAst::buildRunCondition(Scop &S, const isl::ast_build &Build) {  in buildRunCondition()  argument
398   // The conditions that need to be checked at run-time for this scop are  in buildRunCondition()
400   // directly derive a run-time condition.  in buildRunCondition()
401   auto PosCond = Build.expr_from(S.getAssumedContext());  in buildRunCondition()
405     auto ZeroV = isl::val::zero(Build.ctx());  in buildRunCondition()
406     auto NegCond = Build.expr_from(S.getInvalidContext());  in buildRunCondition()
415   // This operation is by construction quadratic in the read-write pointers and  in buildRunCondition()
427             buildCondition(S, Build, RWAccIt0, RWAccIt1).release()));  in buildRunCondition()
431             buildCondition(S, Build, RWAccIt0, &ROAccIt).release()));  in buildRunCondition()
444 ///       original as well as optimized SCoP (e.g., #stride-one-accesses).
454   // The default assumption is that Polly improves the code.  in benefitsFromPolly()
463       [](__isl_keep isl_ast_node *Node, void *User) -> isl_bool {  in walkAstForStatistics()
516   isl_ast_build *Build;  in init()  local
520     Build = isl_ast_build_from_context(S.getContext().release());  in init()
522     Build = isl_ast_build_from_context(  in init()
525   Build = isl_ast_build_set_at_each_domain(Build, AtEachDomain, nullptr);  in init()
532     Build = isl_ast_build_set_before_each_for(Build, &astBuildBeforeFor,  in init()
534     Build =  in init()
535         isl_ast_build_set_after_each_for(Build, &astBuildAfterFor, &BuildInfo);  in init()
537     Build = isl_ast_build_set_before_each_mark(Build, &astBuildBeforeMark,  in init()
540     Build = isl_ast_build_set_after_each_mark(Build, &astBuildAfterMark,  in init()
544   RunCondition = buildRunCondition(S, isl::manage_copy(Build));  in init()
547       isl_ast_build_node_from_schedule(Build, S.getScheduleTree().release()));  in init()
550   isl_ast_build_free(Build);  in init()
575   return Payload && Payload->IsInnermost;  in isInnermost()
585   return Payload && Payload->IsInnermostParallel;  in isInnermostParallel()
590   return Payload && Payload->IsOutermostParallel;  in isOutermostParallel()
595   return Payload && Payload->IsReductionParallel;  in isReductionParallel()
608   //       executed. This can possibly require run-time checks, which again  in isExecutedInParallel()
609   //       raises the question of both run-time check overhead and code size  in isExecutedInParallel()
619   return Payload ? Payload->Build.get_schedule() : isl::union_map();  in getSchedule()
625   return Payload ? Payload->MinimalDependenceDistance : isl::pw_aff();  in getMinimalDependenceDistance()
631   return Payload ? &Payload->BrokenReductions : nullptr;  in getBrokenReductions()
636   return Payload ? Payload->Build : isl::ast_build();  in getBuild()
656       Ast->print(dbgs());  in runIslAst()
664   auto GetDeps = [&](Dependences::AnalysisLevel Lvl) -> const Dependences & {  in run()
682   P = isl_printer_print_str(P, AccessStmt->getBaseName());  in cbPrintUser()
690     if (MemAcc->isRead())  in cbPrintUser()
695     isl::ast_build Build = IslAstInfo::getBuild(isl::manage_copy(Node));  in cbPrintUser()  local
696     if (MemAcc->isAffine()) {  in cbPrintUser()
698           MemAcc->applyScheduleToAccessRelation(Build.get_schedule()).release();  in cbPrintUser()
700       isl::ast_expr AccessExpr = Build.access_from(Pwma);  in cbPrintUser()
704           P, MemAcc->getLatestScopArrayInfo()->getName().c_str());  in cbPrintUser()
710   P = isl_printer_indent(P, -2);  in cbPrintUser()
729           "(use -polly-process-unprofitable to enforce code generation) or "  in print()
731           "-polly-dependences-computeout=0 to set dependence analysis timeout "  in print()
782   auto GetDeps = [this](Dependences::AnalysisLevel Lvl) -> const Dependences & {  in runOnScop()
801   OS << "Printing analysis 'Polly - Generate an AST of the SCoP (isl)'"  in printScop()
804     Ast->print(OS);  in printScop()
809 Pass *polly::createIslAstInfoWrapperPassPass() {  in createIslAstInfoWrapperPassPass()
813 INITIALIZE_PASS_BEGIN(IslAstInfoWrapperPass, "polly-ast",
814                       "Polly - Generate an AST of the SCoP (isl)", false,
818 INITIALIZE_PASS_END(IslAstInfoWrapperPass, "polly-ast",
819                     "Polly - Generate an AST from the SCoP (isl)", false, false)
821 //===----------------------------------------------------------------------===//
857 Pass *polly::createIslAstInfoPrinterLegacyPass(raw_ostream &OS) {  in createIslAstInfoPrinterLegacyPass()
861 INITIALIZE_PASS_BEGIN(IslAstInfoPrinterLegacyPass, "polly-print-ast",
862                       "Polly - Print the AST from a SCoP (isl)", false, false);
864 INITIALIZE_PASS_END(IslAstInfoPrinterLegacyPass, "polly-print-ast",
865                     "Polly - Print the AST from a SCoP (isl)", false, false)