IslAst.cpp File Reference

#include "polly/CodeGen/IslAst.h"
#include "polly/CodeGen/CodeGeneration.h"
#include "polly/DependenceInfo.h"
#include "polly/Options.h"
#include "polly/ScopDetection.h"
#include "polly/ScopInfo.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))
static cl::opt< bool >	PollyPrintAst ("polly-print-ast", cl::desc("Print the ISL abstract syntax tree"), 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 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)

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "polly-ast"

Definition at line 54 of file IslAst.cpp.

Typedef Documentation

IslAstUserPayload

using IslAstUserPayload = IslAstInfo::IslAstUserPayload

Definition at line 59 of file IslAst.cpp.

Function Documentation

astBuildAfterFor()

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

static

Definition at line 278 of file IslAst.cpp.

References __isl_keep, __isl_take, 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()

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

static

Definition at line 313 of file IslAst.cpp.

References __isl_keep, __isl_take, 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()

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

static

Definition at line 251 of file IslAst.cpp.

References __isl_give, __isl_keep, 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()

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

static

Definition at line 299 of file IslAst.cpp.

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

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

astScheduleDimIsParallel()

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 204 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()

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

static

Definition at line 324 of file IslAst.cpp.

References __isl_give, __isl_keep, __isl_take, 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()

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 448 of file IslAst.cpp.

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

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

buildCondition()

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

static

Definition at line 339 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(), S, and isl::set.

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

cbPrintFor()

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 168 of file IslAst.cpp.

References __isl_keep, __isl_take, 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()

__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 665 of file IslAst.cpp.

References __isl_give, __isl_keep, __isl_take, 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()

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

static

References PollyCategory.

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

freeIslAstUserPayload()

void freeIslAstUserPayload ( void * Ptr )

static

Free an IslAstUserPayload object pointed to by Ptr.

Definition at line 124 of file IslAst.cpp.

Referenced by astBuildBeforeFor(), and AtEachDomain().

getBrokenReductionsStr()

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

static

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

Definition at line 140 of file IslAst.cpp.

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

Referenced by cbPrintFor().

PollyParallel()

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

static

References PollyCategory.

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

PollyParallelForce()

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

static

References PollyCategory.

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

PollyPrintAst()

cl::opt< bool > PollyPrintAst ( "polly-print-ast" , cl::desc("Print the ISL abstract syntax tree") , cl::cat(PollyCategory)  )

static

References PollyCategory.

Referenced by polly::runIslAstGen().

PrintAccesses()

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

static

References PollyCategory.

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

printLine()

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 129 of file IslAst.cpp.

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

Referenced by cbPrintFor().

runIslAst()

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

static

Definition at line 642 of file IslAst.cpp.

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

Referenced by polly::runIslAstGen().

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

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

static

References PollyCategory.

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

walkAstForStatistics()

void walkAstForStatistics ( const isl::ast_node & Ast )

static

Collect statistics for the syntax tree rooted at Ast.

Definition at line 462 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().