#include "polly/CodeGen/IslNodeBuilder.h"
#include "polly/CodeGen/BlockGenerators.h"
#include "polly/CodeGen/CodeGeneration.h"
#include "polly/CodeGen/IslAst.h"
#include "polly/CodeGen/IslExprBuilder.h"
#include "polly/CodeGen/LoopGeneratorsGOMP.h"
#include "polly/CodeGen/LoopGeneratorsKMP.h"
#include "polly/CodeGen/RuntimeDebugBuilder.h"
#include "polly/Options.h"
#include "polly/ScopInfo.h"
#include "polly/Support/ISLTools.h"
#include "polly/Support/SCEVValidator.h"
#include "polly/Support/ScopHelper.h"
#include "polly/Support/VirtualInstruction.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "isl/aff.h"
#include "isl/aff_type.h"
#include "isl/ast.h"
#include "isl/ast_build.h"
#include "isl/isl-noexceptions.h"
#include "isl/map.h"
#include "isl/set.h"
#include "isl/union_map.h"
#include "isl/union_set.h"
#include "isl/val.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <string>
#include <utility>
#include <vector>

Macros
#define	DEBUG_TYPE "polly-codegen"

Enumerations
enum class	OpenMPBackend { GNU , LLVM }
	OpenMP backend options. More...

Functions
	STATISTIC (VersionedScops, "Number of SCoPs that required versioning.")

	STATISTIC (SequentialLoops, "Number of generated sequential for-loops")

	STATISTIC (ParallelLoops, "Number of generated parallel for-loops")

	STATISTIC (IfConditions, "Number of generated if-conditions")

static cl::opt< bool >	PollyGenerateRTCPrint ("polly-codegen-emit-rtc-print", cl::desc("Emit code that prints the runtime check result dynamically."), cl::Hidden, cl::cat(PollyCategory))

static cl::opt< bool >	PollyGenerateExpressions ("polly-codegen-generate-expressions", cl::desc("Generate AST expressions for unmodified and modified accesses"), cl::Hidden, cl::cat(PollyCategory))

static cl::opt< int >	PollyTargetFirstLevelCacheLineSize ("polly-target-first-level-cache-line-size", cl::desc("The size of the first level cache line size specified in bytes."), cl::Hidden, cl::init(64), cl::cat(PollyCategory))

static cl::opt< OpenMPBackend >	PollyOmpBackend ("polly-omp-backend", cl::desc("Choose the OpenMP library to use:"), cl::values(clEnumValN(OpenMPBackend::GNU, "GNU", "GNU OpenMP"), clEnumValN(OpenMPBackend::LLVM, "LLVM", "LLVM OpenMP")), cl::Hidden, cl::init(OpenMPBackend::GNU), cl::cat(PollyCategory))

static void	findReferencesByUse (Value SrcVal, ScopStmt UserStmt, Loop UserScope, const ValueMapT &GlobalMap, SetVector< Value > &Values, SetVector< const SCEV * > &SCEVs)

static void	findReferencesInInst (Instruction Inst, ScopStmt UserStmt, Loop UserScope, const ValueMapT &GlobalMap, SetVector< Value > &Values, SetVector< const SCEV * > &SCEVs)

static void	findReferencesInStmt (ScopStmt Stmt, SetVector< Value > &Values, ValueMapT &GlobalMap, SetVector< const SCEV * > &SCEVs)

static void	addReferencesFromStmtSet (isl::set Set, SubtreeReferences *UserPtr)
	Extract the out-of-scop values and SCEVs referenced from a set describing a ScopStmt.

static void	addReferencesFromStmtUnionSet (isl::union_set USet, SubtreeReferences &References)
	Extract the out-of-scop values and SCEVs referenced from a union set referencing multiple ScopStmts.

static bool	IsLoopVectorizerDisabled (isl::ast_node_for Node)
	Restore the initial ordering of dimensions of the band node.

static void	removeSubFuncFromDomTree (Function *F, DominatorTree &DT)
	Remove the BBs contained in a (sub)function from the dominator tree.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "polly-codegen"

Definition at line 74 of file IslNodeBuilder.cpp.

Enumeration Type Documentation

◆ OpenMPBackend

enum class OpenMPBackend

strong

OpenMP backend options.

Enumerator
GNU
LLVM

Definition at line 83 of file IslNodeBuilder.cpp.

Function Documentation

◆ addReferencesFromStmtSet()

static void addReferencesFromStmtSet	(	isl::set	Set,
		SubtreeReferences *	UserPtr
	)

static

Extract the out-of-scop values and SCEVs referenced from a set describing a ScopStmt.

This includes the SCEVUnknowns referenced by the SCEVs used in the statement and the base pointers of the memory accesses. For scalar statements we force the generation of alloca memory locations and list these locations in the set of out-of-scop values as well.

Parameters

Set	A set which references the ScopStmt we are interested in.
UserPtr	A void pointer that can be casted to a SubtreeReferences structure.

Definition at line 286 of file IslNodeBuilder.cpp.

References polly::addReferencesFromStmt(), isl::set::get_tuple_id(), and isl::id::get_user().

Referenced by addReferencesFromStmtUnionSet().

◆ addReferencesFromStmtUnionSet()

static void addReferencesFromStmtUnionSet	(	isl::union_set	USet,
		SubtreeReferences &	References
	)

static

Extract the out-of-scop values and SCEVs referenced from a union set referencing multiple ScopStmts.

This includes the SCEVUnknowns referenced by the SCEVs used in the statement and the base pointers of the memory accesses. For scalar statements we force the generation of alloca memory locations and list these locations in the set of out-of-scop values as well.

Parameters

USet	A union set referencing the ScopStmts we are interested in.
References	The SubtreeReferences data structure through which results are returned and further information is provided.

Definition at line 305 of file IslNodeBuilder.cpp.

References addReferencesFromStmtSet(), and isl::union_set::get_set_list().

Referenced by polly::IslNodeBuilder::getReferencesInSubtree().

◆ findReferencesByUse()

static void findReferencesByUse	(	Value *	SrcVal,
		ScopStmt *	UserStmt,
		Loop *	UserScope,
		const ValueMapT &	GlobalMap,
		SetVector< Value * > &	Values,
		SetVector< const SCEV * > &	SCEVs
	)

static

Definition at line 190 of file IslNodeBuilder.cpp.

References polly::VirtualUse::Block, polly::VirtualUse::Constant, polly::VirtualUse::create(), polly::VirtualUse::getKind(), polly::VirtualUse::getScevExpr(), polly::VirtualUse::Hoisted, polly::VirtualUse::Inter, polly::VirtualUse::Intra, polly::VirtualUse::ReadOnly, polly::VirtualUse::Synthesizable, and polly::Value.

Referenced by findReferencesInInst().

◆ findReferencesInInst()

static void findReferencesInInst	(	Instruction *	Inst,
		ScopStmt *	UserStmt,
		Loop *	UserScope,
		const ValueMapT &	GlobalMap,
		SetVector< Value * > &	Values,
		SetVector< const SCEV * > &	SCEVs
	)

static

Definition at line 219 of file IslNodeBuilder.cpp.

References findReferencesByUse().

Referenced by findReferencesInStmt().

◆ findReferencesInStmt()

static void findReferencesInStmt	(	ScopStmt *	Stmt,
		SetVector< Value * > &	Values,
		ValueMapT &	GlobalMap,
		SetVector< const SCEV * > &	SCEVs
	)

static

Definition at line 227 of file IslNodeBuilder.cpp.

References findReferencesInInst(), polly::ScopStmt::getBasicBlock(), polly::ScopStmt::getInstructions(), polly::Scop::getLI(), polly::ScopStmt::getParent(), polly::ScopStmt::getRegion(), and polly::ScopStmt::isRegionStmt().

Referenced by polly::addReferencesFromStmt().

◆ IsLoopVectorizerDisabled()

static bool IsLoopVectorizerDisabled ( isl::ast_node_for Node )

static

Restore the initial ordering of dimensions of the band node.

In case the band node represents all the dimensions of the iteration domain, recreate the band node to restore the initial ordering of the dimensions.

Parameters

Node	The band node to be modified.

Returns: The modified schedule node.

Definition at line 436 of file IslNodeBuilder.cpp.

References isl::ast_node::as(), assert, isl::ast_node_for::body(), isl::ast_node::get(), isl::ast_node_mark::id(), isl_ast_node_for, isl_ast_node_get_type(), and isl_ast_node_mark.

Referenced by polly::ScopAnnotator::annotateLoopLatch(), and polly::IslNodeBuilder::createForSequential().

◆ PollyGenerateExpressions()

static cl::opt< bool > PollyGenerateExpressions	(	"polly-codegen-generate-expressions"	,
		cl::desc("Generate AST expressions for unmodified and modified accesses")	,
		cl::Hidden	,
		cl::cat(PollyCategory)
	)

static

Referenced by polly::IslNodeBuilder::createNewAccesses().

◆ PollyGenerateRTCPrint()

static cl::opt< bool > PollyGenerateRTCPrint	(	"polly-codegen-emit-rtc-print"	,
		cl::desc("Emit code that prints the runtime check result dynamically.")	,
		cl::Hidden	,
		cl::cat(PollyCategory)
	)

static

Referenced by polly::IslNodeBuilder::createRTC().

◆ PollyOmpBackend()

static cl::opt< OpenMPBackend > PollyOmpBackend	(	"polly-omp-backend"	,
		cl::desc("Choose the OpenMP library to use:")	,
		cl::values(clEnumValN(OpenMPBackend::GNU, "GNU", "GNU OpenMP"), clEnumValN(OpenMPBackend::LLVM, "LLVM", "LLVM OpenMP"))	,
		cl::Hidden	,
		cl::init(OpenMPBackend::GNU)	,
		cl::cat(PollyCategory)
	)

static

Referenced by polly::IslNodeBuilder::createForParallel().

◆ PollyTargetFirstLevelCacheLineSize()

static cl::opt< int > PollyTargetFirstLevelCacheLineSize	(	"polly-target-first-level-cache-line-size"	,
		cl::desc("The size of the first level cache line size specified in bytes.")	,
		cl::Hidden	,
		cl::init(64)	,
		cl::cat(PollyCategory)
	)

static

Referenced by polly::IslNodeBuilder::allocateNewArrays().

◆ removeSubFuncFromDomTree()

static void removeSubFuncFromDomTree	(	Function *	F,
		DominatorTree &	DT
	)

static

Remove the BBs contained in a (sub)function from the dominator tree.

This function removes the basic blocks that are part of a subfunction from the dominator tree. Specifically, when generating code it may happen that at some point the code generation continues in a new sub-function (e.g., when generating OpenMP code). The basic blocks that are created in this sub-function are then still part of the dominator tree of the original function, such that the dominator tree reaches over function boundaries. This is not only incorrect, but also causes crashes. This function now removes from the dominator tree all basic blocks that are dominated (and consequently reachable) from the entry block of this (sub)function.

FIXME: A LLVM (function or region) pass should not touch anything outside of the function/region it runs on. Hence, the pure need for this function shows that we do not comply to this rule. At the moment, this does not cause any issues, but we should be aware that such issues may appear. Unfortunately the current LLVM pass infrastructure does not allow to make Polly a module or call-graph pass to solve this issue, as such a pass would not have access to the per-function analyses passes needed by Polly. A future pass manager infrastructure is supposed to enable such kind of access possibly allowing us to create a cleaner solution here.

FIXME: Instead of adding the dominance information and then dropping it later on, we should try to just not add it in the first place. This requires some careful testing to make sure this does not break in interaction with the SCEVBuilder and SplitBlock which may rely on the dominator tree or which may try to update it.

Parameters

F	The function which contains the BBs to removed.
DT	The dominator tree from which to remove the BBs.

Definition at line 539 of file IslNodeBuilder.cpp.

References N().

Referenced by polly::IslNodeBuilder::createForParallel().

◆ STATISTIC() [1/4]

STATISTIC	(	IfConditions	,
		"Number of generated if-conditions"
	)

◆ STATISTIC() [2/4]

STATISTIC	(	ParallelLoops	,
		"Number of generated parallel for-loops"
	)

◆ STATISTIC() [3/4]

STATISTIC	(	SequentialLoops	,
		"Number of generated sequential for-loops"
	)

◆ STATISTIC() [4/4]

STATISTIC	(	VersionedScops	,
		"Number of SCoPs that required versioning."
	)

Macros

Enumerations

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Enumeration Type Documentation

◆ OpenMPBackend

Function Documentation

◆ addReferencesFromStmtSet()

◆ addReferencesFromStmtUnionSet()

◆ findReferencesByUse()

◆ findReferencesInInst()

◆ findReferencesInStmt()

◆ IsLoopVectorizerDisabled()

◆ PollyGenerateExpressions()

◆ PollyGenerateRTCPrint()

◆ PollyOmpBackend()

◆ PollyTargetFirstLevelCacheLineSize()

◆ removeSubFuncFromDomTree()

◆ STATISTIC() [1/4]

◆ STATISTIC() [2/4]

◆ STATISTIC() [3/4]

◆ STATISTIC() [4/4]