IslAst.cpp | Explore in Territory

//===- IslAst.cpp - isl code generator interface --------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// The isl code generator interface takes a Scop and generates an isl_ast. This
// ist_ast can either be returned directly or it can be pretty printed to
// stdout.
//
// A typical isl_ast output looks like this:
//
// for (c2 = max(0, ceild(n + m, 2); c2 <= min(511, floord(5 * n, 3)); c2++) {
//   bb2(c2);
// }
//
// An in-depth discussion of our AST generation approach can be found in:
//
// Polyhedral AST generation is more than scanning polyhedra
// Tobias Grosser, Sven Verdoolaege, Albert Cohen
// ACM Transactions on Programming Languages and Systems (TOPLAS),
// 37(4), July 2015
// http://www.grosser.es/#pub-polyhedral-AST-generation
//
//===----------------------------------------------------------------------===//

#include "polly/CodeGen/IslAst.h"
#include "polly/CodeGen/CodeGeneration.h"
#include "polly/DependenceInfo.h"
#include "polly/LinkAllPasses.h"
#include "polly/Options.h"
#include "polly/ScopDetection.h"
#include "polly/ScopInfo.h"
#include "polly/ScopPass.h"
#include "polly/Support/GICHelper.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "isl/aff.h"
#include "isl/ast.h"
#include "isl/ast_build.h"
#include "isl/id.h"
#include "isl/isl-noexceptions.h"
#include "isl/printer.h"
#include "isl/schedule.h"
#include "isl/set.h"
#include "isl/union_map.h"
#include "isl/val.h"
#include <cassert>
#include <cstdlib>

#include "polly/Support/PollyDebug.h"
#define DEBUG_TYPE …

usingnamespacellvm;
usingnamespacepolly;

IslAstUserPayload;

static cl::opt<bool>
    PollyParallel("polly-parallel",
                  cl::desc("Generate thread parallel code (isl codegen only)"),
                  cl::cat(PollyCategory));

static cl::opt<bool> PrintAccesses("polly-ast-print-accesses",
                                   cl::desc("Print memory access functions"),
                                   cl::cat(PollyCategory));

static cl::opt<bool> PollyParallelForce(
    "polly-parallel-force",
    cl::desc(
        "Force generation of thread parallel code ignoring any cost model"),
    cl::cat(PollyCategory));

static cl::opt<bool> UseContext("polly-ast-use-context",
                                cl::desc("Use context"), cl::Hidden,
                                cl::init(true), cl::cat(PollyCategory));

static cl::opt<bool> DetectParallel("polly-ast-detect-parallel",
                                    cl::desc("Detect parallelism"), cl::Hidden,
                                    cl::cat(PollyCategory));

STATISTIC(ScopsProcessed, "Number of SCoPs processed");
STATISTIC(ScopsBeneficial, "Number of beneficial SCoPs");
STATISTIC(BeneficialAffineLoops, "Number of beneficial affine loops");
STATISTIC(BeneficialBoxedLoops, "Number of beneficial boxed loops");

STATISTIC(NumForLoops, "Number of for-loops");
STATISTIC(NumParallel, "Number of parallel for-loops");
STATISTIC(NumInnermostParallel, "Number of innermost parallel for-loops");
STATISTIC(NumOutermostParallel, "Number of outermost parallel for-loops");
STATISTIC(NumReductionParallel, "Number of reduction-parallel for-loops");
STATISTIC(NumExecutedInParallel, "Number of for-loops executed in parallel");
STATISTIC(NumIfConditions, "Number of if-conditions");

namespace polly {

/// Temporary information used when building the ast.
struct AstBuildUserInfo { … };
} // namespace polly

/// Free an IslAstUserPayload object pointed to by @p Ptr.
static void freeIslAstUserPayload(void *Ptr) { … }

/// Print a string @p str in a single line using @p Printer.
static isl_printer *printLine(__isl_take isl_printer *Printer,
                              const std::string &str,
                              __isl_keep isl_pw_aff *PWA = nullptr) { … }

/// Return all broken reductions as a string of clauses (OpenMP style).
static const std::string getBrokenReductionsStr(const isl::ast_node &Node) { … }

/// 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 *) { … }

/// 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
/// to check are actually the union of the transitive closure of the initial
/// reduction dependences together with their reversal. Even though these
/// dependences connect all iterations with each other (thus they are cyclic)
/// we can perform the parallelism check as we are only interested in a zero
/// (or non-zero) dependence distance on the dimension in question.
static bool astScheduleDimIsParallel(const isl::ast_build &Build,
                                     const Dependences *D,
                                     IslAstUserPayload *NodeInfo) { … }

// This method is executed before the construction of a for node. It creates
// an isl_id that is used to annotate the subsequently generated ast for nodes.
//
// In this function we also run the following analyses:
//
// - Detection of openmp parallel loops
//
static __isl_give isl_id *astBuildBeforeFor(__isl_keep isl_ast_build *Build,
                                            void *User) { … }

// This method is executed after the construction of a for node.
//
// It performs the following actions:
//
// - Reset the 'InParallelFor' flag, as soon as we leave a for node,
//   that is marked as openmp parallel.
//
static __isl_give isl_ast_node *
astBuildAfterFor(__isl_take isl_ast_node *Node, __isl_keep isl_ast_build *Build,
                 void *User) { … }

static isl_stat astBuildBeforeMark(__isl_keep isl_id *MarkId,
                                   __isl_keep isl_ast_build *Build,
                                   void *User) { … }

static __isl_give isl_ast_node *
astBuildAfterMark(__isl_take isl_ast_node *Node,
                  __isl_keep isl_ast_build *Build, void *User) { … }

static __isl_give isl_ast_node *AtEachDomain(__isl_take isl_ast_node *Node,
                                             __isl_keep isl_ast_build *Build,
                                             void *User) { … }

// Build alias check condition given a pair of minimal/maximal access.
static isl::ast_expr buildCondition(Scop &S, isl::ast_build Build,
                                    const Scop::MinMaxAccessTy *It0,
                                    const Scop::MinMaxAccessTy *It1) { … }

isl::ast_expr IslAst::buildRunCondition(Scop &S, const isl::ast_build &Build) { … }

/// Simple cost analysis for a given SCoP.
///
/// TODO: Improve this analysis and extract it to make it usable in other
///       places too.
///       In order to improve the cost model we could either keep track of
///       performed optimizations (e.g., tiling) or compute properties on the
///       original as well as optimized SCoP (e.g., #stride-one-accesses).
static bool benefitsFromPolly(Scop &Scop, bool PerformParallelTest) { … }

/// Collect statistics for the syntax tree rooted at @p Ast.
static void walkAstForStatistics(const isl::ast_node &Ast) { … }

IslAst::IslAst(Scop &Scop) : … { … }

IslAst::IslAst(IslAst &&O)
    : … { … }

void IslAst::init(const Dependences &D) { … }

IslAst IslAst::create(Scop &Scop, const Dependences &D) { … }

isl::ast_node IslAst::getAst() { … }
isl::ast_expr IslAst::getRunCondition() { … }

isl::ast_node IslAstInfo::getAst() { … }
isl::ast_expr IslAstInfo::getRunCondition() { … }

IslAstUserPayload *IslAstInfo::getNodePayload(const isl::ast_node &Node) { … }

bool IslAstInfo::isInnermost(const isl::ast_node &Node) { … }

bool IslAstInfo::isParallel(const isl::ast_node &Node) { … }

bool IslAstInfo::isInnermostParallel(const isl::ast_node &Node) { … }

bool IslAstInfo::isOutermostParallel(const isl::ast_node &Node) { … }

bool IslAstInfo::isReductionParallel(const isl::ast_node &Node) { … }

bool IslAstInfo::isExecutedInParallel(const isl::ast_node &Node) { … }

isl::union_map IslAstInfo::getSchedule(const isl::ast_node &Node) { … }

isl::pw_aff
IslAstInfo::getMinimalDependenceDistance(const isl::ast_node &Node) { … }

IslAstInfo::MemoryAccessSet *
IslAstInfo::getBrokenReductions(const isl::ast_node &Node) { … }

isl::ast_build IslAstInfo::getBuild(const isl::ast_node &Node) { … }

static std::unique_ptr<IslAstInfo> runIslAst(
    Scop &Scop,
    function_ref<const Dependences &(Dependences::AnalysisLevel)> GetDeps) { … }

IslAstInfo IslAstAnalysis::run(Scop &S, ScopAnalysisManager &SAM,
                               ScopStandardAnalysisResults &SAR) { … }

static __isl_give isl_printer *cbPrintUser(__isl_take isl_printer *P,
                                           __isl_take isl_ast_print_options *O,
                                           __isl_keep isl_ast_node *Node,
                                           void *User) { … }

void IslAstInfo::print(raw_ostream &OS) { … }

AnalysisKey IslAstAnalysis::Key;
PreservedAnalyses IslAstPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
                                         ScopStandardAnalysisResults &SAR,
                                         SPMUpdater &U) { … }

void IslAstInfoWrapperPass::releaseMemory() { … }

bool IslAstInfoWrapperPass::runOnScop(Scop &Scop) { … }

void IslAstInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

void IslAstInfoWrapperPass::printScop(raw_ostream &OS, Scop &S) const { … }

char IslAstInfoWrapperPass::ID = …;

Pass *polly::createIslAstInfoWrapperPassPass() { … }

INITIALIZE_PASS_BEGIN(IslAstInfoWrapperPass, "polly-ast",
                      "Polly - Generate an AST of the SCoP (isl)", false,
                      false);
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
INITIALIZE_PASS_END(IslAstInfoWrapperPass, "polly-ast",
                    "Polly - Generate an AST from the SCoP (isl)", false, false)

//===----------------------------------------------------------------------===//

namespace {
/// Print result from IslAstInfoWrapperPass.
class IslAstInfoPrinterLegacyPass final : public ScopPass { … };

char IslAstInfoPrinterLegacyPass::ID = …;
} // namespace

Pass *polly::createIslAstInfoPrinterLegacyPass(raw_ostream &OS) { … }

INITIALIZE_PASS_BEGIN(IslAstInfoPrinterLegacyPass, "polly-print-ast",
                      "Polly - Print the AST from a SCoP (isl)", false, false);
INITIALIZE_PASS_DEPENDENCY(IslAstInfoWrapperPass);
INITIALIZE_PASS_END(IslAstInfoPrinterLegacyPass, "polly-print-ast",
                    "Polly - Print the AST from a SCoP (isl)", false, false)
llvm/polly/lib/CodeGen/IslAst.cpp
