Polly 20.0.0git
Classes | Namespaces | Macros | Typedefs | Functions
IslAst.cpp File Reference
#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"

Go to the source code of this file.

Classes

struct  polly::AstBuildUserInfo
 Temporary information used when building the ast. More...
 

Namespaces

namespace  polly
 

Macros

#define DEBUG_TYPE   "polly-ast"
 

Typedefs

using IslAstUserPayload = IslAstInfo::IslAstUserPayload
 

Functions

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")
 
static void freeIslAstUserPayload (void *Ptr)
 Free an IslAstUserPayload object pointed to by Ptr.
 
static isl_printer * printLine (__isl_take isl_printer *Printer, const std::string &str, __isl_keep isl_pw_aff *PWA=nullptr)
 Print a string str in a single line using Printer.
 
static const std::string getBrokenReductionsStr (const isl::ast_node &Node)
 Return all broken reductions as a string of clauses (OpenMP style).
 
static isl_printer * cbPrintFor (__isl_take isl_printer *Printer, __isl_take isl_ast_print_options *Options, __isl_keep isl_ast_node *Node, void *)
 Callback executed for each for node in the ast in order to print it.
 
static bool astScheduleDimIsParallel (const isl::ast_build &Build, const Dependences *D, IslAstUserPayload *NodeInfo)
 Check if the current scheduling dimension is parallel.
 
static __isl_give isl_id * astBuildBeforeFor (__isl_keep isl_ast_build *Build, void *User)
 
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)
 
static isl::ast_expr buildCondition (Scop &S, isl::ast_build Build, const Scop::MinMaxAccessTy *It0, const Scop::MinMaxAccessTy *It1)
 
static bool benefitsFromPolly (Scop &Scop, bool PerformParallelTest)
 Simple cost analysis for a given SCoP.
 
static void walkAstForStatistics (const isl::ast_node &Ast)
 Collect statistics for the syntax tree rooted at Ast.
 
static std::unique_ptr< IslAstInfo > runIslAst (Scop &Scop, function_ref< const Dependences &(Dependences::AnalysisLevel)> GetDeps)
 
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)
 
 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
 
 INITIALIZE_PASS_BEGIN (IslAstInfoPrinterLegacyPass, "polly-print-ast", "Polly - Print the AST from a SCoP (isl)", false, false)
 
 INITIALIZE_PASS_DEPENDENCY (IslAstInfoWrapperPass)
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "polly-ast"

Definition at line 56 of file IslAst.cpp.

Typedef Documentation

◆ IslAstUserPayload

using IslAstUserPayload = IslAstInfo::IslAstUserPayload

Definition at line 61 of file IslAst.cpp.

Function Documentation

◆ astBuildAfterFor()

static __isl_give isl_ast_node * astBuildAfterFor ( __isl_take isl_ast_node *  Node,
__isl_keep isl_ast_build *  Build,
void *  User 
)
static

Definition at line 275 of file IslAst.cpp.

References assert, polly::IslAstInfo::IslAstUserPayload::Build, polly::AstBuildUserInfo::InParallelFor, polly::AstBuildUserInfo::InSIMD, isl::ast_build::is_null(), polly::IslAstInfo::IslAstUserPayload::IsInnermost, polly::IslAstInfo::IslAstUserPayload::IsInnermostParallel, isl_ast_node_get_annotation(), isl_id_free(), isl_id_get_user(), polly::IslAstInfo::IslAstUserPayload::IsOutermostParallel, polly::IslAstInfo::IslAstUserPayload::IsParallel, polly::AstBuildUserInfo::LastForNodeId, and isl::manage_copy().

Referenced by polly::IslAst::init().

◆ astBuildAfterMark()

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

Definition at line 310 of file IslAst.cpp.

References assert, polly::AstBuildUserInfo::InSIMD, isl_ast_node_get_type(), isl_ast_node_mark, isl_ast_node_mark_get_id(), isl_id_free(), and isl_id_get_name().

Referenced by polly::IslAst::init().

◆ astBuildBeforeFor()

static __isl_give isl_id * astBuildBeforeFor ( __isl_keep isl_ast_build *  Build,
void *  User 
)
static

Definition at line 248 of file IslAst.cpp.

References astScheduleDimIsParallel(), polly::AstBuildUserInfo::Deps, freeIslAstUserPayload(), polly::AstBuildUserInfo::InParallelFor, polly::AstBuildUserInfo::InSIMD, isl_ast_build_get_ctx(), isl_id_alloc(), isl_id_set_free_user(), polly::IslAstInfo::IslAstUserPayload::IsOutermostParallel, polly::IslAstInfo::IslAstUserPayload::IsParallel, polly::AstBuildUserInfo::LastForNodeId, and isl::manage_copy().

Referenced by polly::IslAst::init().

◆ astBuildBeforeMark()

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

Definition at line 296 of file IslAst.cpp.

References polly::AstBuildUserInfo::InSIMD, isl_id_get_name(), isl_stat_error, and isl_stat_ok.

Referenced by polly::IslAst::init().

◆ astScheduleDimIsParallel()

static bool astScheduleDimIsParallel ( const isl::ast_build &  Build,
const Dependences *  D,
IslAstUserPayload *  NodeInfo 
)
static

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, 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.

Definition at line 201 of file IslAst.cpp.

References polly::IslAstInfo::IslAstUserPayload::BrokenReductions, isl::union_map::get(), isl::ast_build::get_schedule(), polly::Dependences::getDependences(), polly::Dependences::getReductionDependences(), polly::Dependences::hasValidDependences(), polly::Dependences::isParallel(), polly::IslAstInfo::IslAstUserPayload::IsReductionParallel, isl::manage(), isl::manage_copy(), polly::IslAstInfo::IslAstUserPayload::MinimalDependenceDistance, isl::union_map::release(), polly::Dependences::TYPE_RAW, polly::Dependences::TYPE_TC_RED, polly::Dependences::TYPE_WAR, and polly::Dependences::TYPE_WAW.

Referenced by astBuildBeforeFor().

◆ AtEachDomain()

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

Definition at line 321 of file IslAst.cpp.

References assert, polly::IslAstInfo::IslAstUserPayload::Build, freeIslAstUserPayload(), isl_ast_build_get_ctx(), isl_ast_node_get_annotation(), isl_ast_node_set_annotation(), isl_id_alloc(), isl_id_set_free_user(), and isl::manage_copy().

Referenced by polly::IslAst::init().

◆ benefitsFromPolly()

static bool benefitsFromPolly ( Scop &  Scop,
bool  PerformParallelTest 
)
static

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).

Definition at line 445 of file IslAst.cpp.

References polly::Scop::getAliasGroups(), polly::Scop::isOptimized(), and polly::PollyProcessUnprofitable.

Referenced by polly::IslAst::init().

◆ buildCondition()

static isl::ast_expr buildCondition ( Scop &  S,
isl::ast_build  Build,
const Scop::MinMaxAccessTy *  It0,
const Scop::MinMaxAccessTy *  It1 
)
static

Definition at line 336 of file IslAst.cpp.

References isl::ast_build::access_from(), isl::ast_expr::address_of(), isl::ast_build::ctx(), isl::pw_multi_aff::domain(), isl::ast_expr::from_val(), isl::pw_multi_aff::get_tuple_id(), polly::ScopArrayInfo::getBasePtrOriginSAI(), polly::ScopArrayInfo::getFromId(), isl::val::int_from_ui(), isl::pw_multi_aff::intersect_params(), isl::set::is_empty(), isl::ast_expr::is_null(), isl_ast_expr_or(), isl::ast_expr::le(), isl::manage(), isl::ast_expr::release(), and isl::set.

Referenced by polly::IslAst::buildRunCondition().

◆ cbPrintFor()

static isl_printer * cbPrintFor ( __isl_take isl_printer *  Printer,
__isl_take isl_ast_print_options *  Options,
__isl_keep isl_ast_node *  Node,
void *   
)
static

Callback executed for each for node in the ast in order to print it.

Definition at line 165 of file IslAst.cpp.

References isl::pw_aff::get(), getBrokenReductionsStr(), polly::IslAstInfo::getMinimalDependenceDistance(), isl::pw_aff::is_null(), polly::IslAstInfo::isExecutedInParallel(), polly::IslAstInfo::isInnermostParallel(), isl_ast_node_for_print(), polly::IslAstInfo::isOutermostParallel(), isl::manage_copy(), and printLine().

Referenced by polly::IslAstInfo::print().

◆ cbPrintUser()

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 
)
static

Definition at line 671 of file IslAst.cpp.

References isl::ast_build::access_from(), isl::ast_node_user::expr(), isl::ast_expr::get(), isl::ast_expr::get_id(), isl::ast_expr::get_op_arg(), isl::ast_build::get_schedule(), isl::id::get_user(), polly::ScopStmt::getBaseName(), polly::IslAstInfo::getBuild(), isl_ast_print_options_free(), isl_printer_end_line(), isl_printer_indent(), isl_printer_print_ast_expr(), isl_printer_print_str(), isl_printer_start_line(), isl::manage(), and isl::manage_copy().

Referenced by polly::IslAstInfo::print().

◆ DetectParallel()

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

Referenced by polly::IslAst::init().

◆ freeIslAstUserPayload()

static void freeIslAstUserPayload ( void *  Ptr)
static

Free an IslAstUserPayload object pointed to by Ptr.

Definition at line 121 of file IslAst.cpp.

Referenced by astBuildBeforeFor(), and AtEachDomain().

◆ getBrokenReductionsStr()

static const std::string getBrokenReductionsStr ( const isl::ast_node &  Node)
static

Return all broken reductions as a string of clauses (OpenMP style).

Definition at line 137 of file IslAst.cpp.

References polly::IslAstInfo::getBrokenReductions(), polly::MemoryAccess::getReductionOperatorStr(), and str.

Referenced by cbPrintFor().

◆ INITIALIZE_PASS_BEGIN() [1/2]

INITIALIZE_PASS_BEGIN ( IslAstInfoPrinterLegacyPass  ,
"polly-print-ast"  ,
"Polly - Print the AST from a SCoP (isl)"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_BEGIN() [2/2]

INITIALIZE_PASS_BEGIN ( IslAstInfoWrapperPass  ,
"polly-ast"  ,
"Polly - Generate an AST of the SCoP (isl)"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_DEPENDENCY() [1/3]

INITIALIZE_PASS_DEPENDENCY ( DependenceInfo  )

◆ INITIALIZE_PASS_DEPENDENCY() [2/3]

INITIALIZE_PASS_DEPENDENCY ( IslAstInfoWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [3/3]

INITIALIZE_PASS_DEPENDENCY ( ScopInfoRegionPass  )

◆ INITIALIZE_PASS_END()

INITIALIZE_PASS_END ( IslAstInfoWrapperPass  ,
"polly-ast"  ,
"Polly - Generate an AST from the SCoP (isl)"  ,
false  ,
false   
)

Print result from IslAstInfoWrapperPass.

Definition at line 818 of file IslAst.cpp.

References polly::ScopPass::getAnalysisUsage(), and polly::IslAstInfoWrapperPass::printScop().

◆ PollyParallel()

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

Referenced by polly::IslAst::init(), and polly::IslAstInfo::isExecutedInParallel().

◆ PollyParallelForce()

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

Referenced by polly::IslAstInfo::isExecutedInParallel().

◆ PrintAccesses()

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

Referenced by polly::IslAstInfo::print().

◆ printLine()

static isl_printer * printLine ( __isl_take isl_printer *  Printer,
const std::string &  str,
__isl_keep isl_pw_aff *  PWA = nullptr 
)
static

Print a string str in a single line using Printer.

Definition at line 126 of file IslAst.cpp.

References isl_printer_end_line(), isl_printer_print_pw_aff(), isl_printer_print_str(), isl_printer_start_line(), and str.

Referenced by cbPrintFor().

◆ runIslAst()

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

Definition at line 639 of file IslAst.cpp.

References polly::Dependences::AL_Statement, polly::Dependences::getSharedIslCtx(), polly::Scop::getSharedIslCtx(), and POLLY_DEBUG.

Referenced by polly::IslAstAnalysis::run(), and polly::IslAstInfoWrapperPass::runOnScop().

◆ STATISTIC() [1/11]

STATISTIC ( BeneficialAffineLoops  ,
"Number of beneficial affine loops"   
)

◆ STATISTIC() [2/11]

STATISTIC ( BeneficialBoxedLoops  ,
"Number of beneficial boxed loops"   
)

◆ STATISTIC() [3/11]

STATISTIC ( NumExecutedInParallel  ,
"Number of for-loops executed in parallel"   
)

◆ STATISTIC() [4/11]

STATISTIC ( NumForLoops  ,
"Number of for-loops"   
)

◆ STATISTIC() [5/11]

STATISTIC ( NumIfConditions  ,
"Number of if-conditions"   
)

◆ STATISTIC() [6/11]

STATISTIC ( NumInnermostParallel  ,
"Number of innermost parallel for-loops"   
)

◆ STATISTIC() [7/11]

STATISTIC ( NumOutermostParallel  ,
"Number of outermost parallel for-loops"   
)

◆ STATISTIC() [8/11]

STATISTIC ( NumParallel  ,
"Number of parallel for-loops"   
)

◆ STATISTIC() [9/11]

STATISTIC ( NumReductionParallel  ,
"Number of reduction-parallel for-loops"   
)

◆ STATISTIC() [10/11]

STATISTIC ( ScopsBeneficial  ,
"Number of beneficial SCoPs"   
)

◆ STATISTIC() [11/11]

STATISTIC ( ScopsProcessed  ,
"Number of SCoPs processed"   
)

◆ UseContext()

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

Referenced by polly::IslAst::init().

◆ walkAstForStatistics()

static void walkAstForStatistics ( const isl::ast_node &  Ast)
static

Collect statistics for the syntax tree rooted at Ast.

Definition at line 459 of file IslAst.cpp.

References __isl_keep, assert, isl::ast_node::get(), isl::ast_node::is_null(), isl_ast_node_foreach_descendant_top_down(), and isl_bool_true.

Referenced by polly::IslAst::init().

Generated on Wed Nov 13 2024 03:17:32 for Polly by doxygen 1.9.6