Generate a new basic block for a polyhedral statement. More...

#include <BlockGenerators.h>

Inheritance diagram for polly::BlockGenerator:

Public Types
typedef llvm::SmallVector< ValueMapT, 8 >	VectorValueMapT


using	AllocaMapTy = DenseMap< const ScopArrayInfo *, AssertingVH< AllocaInst > >
	Map types to resolve scalar dependences.

using	EscapeUserVectorTy = SmallVector< Instruction *, 4 >
	Simple vector of instructions to store escape users.

using	EscapeUsersAllocaMapTy = MapVector< Instruction *, std::pair< AssertingVH< Value >, EscapeUserVectorTy > >
	Map type to resolve escaping users for scalar instructions.

Public Member Functions
	BlockGenerator (PollyIRBuilder &Builder, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap, ValueMapT &GlobalMap, IslExprBuilder ExprBuilder, BasicBlock StartBlock)
	Create a generator for basic blocks.

void	copyStmt (ScopStmt &Stmt, LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses)
	Copy the basic block.

void	freeScalarAlloc (ScopArrayInfo *Array)
	Remove a ScopArrayInfo's allocation from the ScalarMap.

Value *	getOrCreateAlloca (const MemoryAccess &Access)
	Return the alloca for `Access`.

Value *	getOrCreateAlloca (const ScopArrayInfo *Array)
	Return the alloca for `Array`.

void	finalizeSCoP (Scop &S)
	Finalize the code generation for the SCoP `S`.

virtual	~BlockGenerator ()
	An empty destructor.

	BlockGenerator (const BlockGenerator &)=default

BasicBlock *	splitBB (BasicBlock *BB)
	Split `BB` to create a new one we can use to clone `BB` in.

void	switchGeneratedFunc (Function GenFn, DominatorTree GenDT, LoopInfo GenLI, ScalarEvolution GenSE)
	Change the function that code is emitted into.

BasicBlock *	copyBB (ScopStmt &Stmt, BasicBlock BB, ValueMapT &BBMap, LoopToScevMapT &LTS, isl_id_to_ast_expr NewAccesses)
	Copy the given basic block.

void	copyBB (ScopStmt &Stmt, BasicBlock BB, BasicBlock BBCopy, ValueMapT &BBMap, LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses)
	Copy the given basic block.

void	generateScalarLoads (ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap, __isl_keep isl_id_to_ast_expr *NewAccesses)
	Generate reload of scalars demoted to memory and needed by `Stmt`.

void	generateBeginStmtTrace (ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap)
	When statement tracing is enabled, build the print instructions for printing the current statement instance.

Value *	buildContainsCondition (ScopStmt &Stmt, const isl::set &Subdomain)
	Generate instructions that compute whether one instance of `Set` is executed.

void	generateConditionalExecution (ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject, const std::function< void()> &GenThenFunc)
	Generate code that executes in a subset of `Stmt's` domain.

virtual void	generateScalarStores (ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap, __isl_keep isl_id_to_ast_expr *NewAccesses)
	Generate the scalar stores for the given statement.

void	handleOutsideUsers (const Scop &S, ScopArrayInfo *Array)
	Handle users of `Array` outside the SCoP.

void	findOutsideUsers (Scop &S)
	Find scalar statements that have outside users.

void	createScalarInitialization (Scop &S)
	Initialize the memory of demoted scalars.

void	createExitPHINodeMerges (Scop &S)
	Create exit PHI node merges for PHI nodes with more than two edges from inside the scop.

void	createScalarFinalization (Scop &S)
	Promote the values of demoted scalars after the SCoP.

Value *	trySynthesizeNewValue (ScopStmt &Stmt, Value Old, ValueMapT &BBMap, LoopToScevMapT &LTS, Loop L) const
	Try to synthesize a new value.

Value *	getNewValue (ScopStmt &Stmt, Value Old, ValueMapT &BBMap, LoopToScevMapT &LTS, Loop L) const
	Get the new version of a value.

void	copyInstScalar (ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap, LoopToScevMapT &LTS)

Loop *	getLoopForStmt (const ScopStmt &Stmt) const
	Get the innermost loop that surrounds the statement `Stmt`.

Value *	generateLocationAccessed (ScopStmt &Stmt, MemAccInst Inst, ValueMapT &BBMap, LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses)
	Generate the operand address.

Value *	generateLocationAccessed (ScopStmt &Stmt, Loop L, Value Pointer, ValueMapT &BBMap, LoopToScevMapT &LTS, isl_id_to_ast_expr NewAccesses, __isl_take isl_id Id, Type *ExpectedType)
	Generate the operand address.

Value *	getImplicitAddress (MemoryAccess &Access, Loop L, LoopToScevMapT &LTS, ValueMapT &BBMap, __isl_keep isl_id_to_ast_expr NewAccesses)
	Generate the pointer value that is accesses by `Access`.

Value *	generateArrayLoad (ScopStmt &Stmt, LoadInst load, ValueMapT &BBMap, LoopToScevMapT &LTS, isl_id_to_ast_expr NewAccesses)

void	generateArrayStore (ScopStmt &Stmt, StoreInst store, ValueMapT &BBMap, LoopToScevMapT &LTS, isl_id_to_ast_expr NewAccesses)

virtual void	copyPHIInstruction (ScopStmt &, PHINode *, ValueMapT &, LoopToScevMapT &)
	Copy a single PHI instruction.

void	copyInstruction (ScopStmt &Stmt, Instruction Inst, ValueMapT &BBMap, LoopToScevMapT &LTS, isl_id_to_ast_expr NewAccesses)
	Copy a single Instruction.

bool	canSyntheziseInStmt (ScopStmt &Stmt, Instruction *Inst)
	Helper to determine if `Inst` can be synthesized in `Stmt`.

void	removeDeadInstructions (BasicBlock *BB, ValueMapT &BBMap)
	Remove dead instructions generated for BB.

void	invalidateScalarEvolution (Scop &S)
	Invalidate the scalar evolution expressions for a scop.

Public Attributes
AllocaMapTy &	ScalarMap
	Map to resolve scalar dependences for PHI operands and scalars.

EscapeUsersAllocaMapTy &	EscapeMap
	Map from instructions to their escape users as well as the alloca.

ValueMapT &	GlobalMap
	A map from llvm::Values referenced in the old code to a new set of llvm::Values, which is used to replace these old values during code generation.

BasicBlock *	StartBlock
	The first basic block after the RTC.

Protected Attributes
PollyIRBuilder &	Builder

LoopInfo &	LI

ScalarEvolution &	SE

IslExprBuilder *	ExprBuilder

DominatorTree &	DT
	The dominator tree of this function.


DominatorTree *	GenDT
	Relates to the region where the code is emitted into.

LoopInfo *	GenLI

ScalarEvolution *	GenSE

Detailed Description

Generate a new basic block for a polyhedral statement.

Definition at line 55 of file BlockGenerators.h.

Member Typedef Documentation

◆ AllocaMapTy

using polly::BlockGenerator::AllocaMapTy = DenseMap<const ScopArrayInfo *, AssertingVH<AllocaInst> >

Map types to resolve scalar dependences.

Definition at line 62 of file BlockGenerators.h.

◆ EscapeUsersAllocaMapTy

using polly::BlockGenerator::EscapeUsersAllocaMapTy = MapVector<Instruction *, std::pair<AssertingVH<Value>, EscapeUserVectorTy> >

Map type to resolve escaping users for scalar instructions.

See also: The EscapeMap member.

Definition at line 70 of file BlockGenerators.h.

◆ EscapeUserVectorTy

using polly::BlockGenerator::EscapeUserVectorTy = SmallVector<Instruction *, 4>

Simple vector of instructions to store escape users.

Definition at line 65 of file BlockGenerators.h.

◆ VectorValueMapT

typedef llvm::SmallVector<ValueMapT, 8> polly::BlockGenerator::VectorValueMapT

Definition at line 57 of file BlockGenerators.h.

Constructor & Destructor Documentation

◆ BlockGenerator() [1/2]

BlockGenerator::BlockGenerator	(	PollyIRBuilder &	Builder,
		LoopInfo &	LI,
		ScalarEvolution &	SE,
		DominatorTree &	DT,
		AllocaMapTy &	ScalarMap,
		EscapeUsersAllocaMapTy &	EscapeMap,
		ValueMapT &	GlobalMap,
		IslExprBuilder *	ExprBuilder,
		BasicBlock *	StartBlock
	)

Create a generator for basic blocks.

Parameters

Builder	The LLVM-IR Builder used to generate the statement. The code is generated at the location, the Builder points to.
LI	The loop info for the current function
SE	The scalar evolution info for the current function
DT	The dominator tree of this function.
ScalarMap	Map from scalars to their demoted location.
EscapeMap	Map from scalars to their escape users and locations.
GlobalMap	A mapping from llvm::Values used in the original scop region to a new set of llvm::Values. Each reference to an original value appearing in this mapping is replaced with the new value it is mapped to.
ExprBuilder	An expression builder to generate new access functions.
StartBlock	The first basic block after the RTC.

Definition at line 56 of file BlockGenerators.cpp.

◆ ~BlockGenerator()

virtual polly::BlockGenerator::~BlockGenerator ( )

inlinevirtual

An empty destructor.

Definition at line 152 of file BlockGenerators.h.

◆ BlockGenerator() [2/2]

polly::BlockGenerator::BlockGenerator ( const BlockGenerator & )

default

Member Function Documentation

◆ buildContainsCondition()

Value * BlockGenerator::buildContainsCondition	(	ScopStmt &	Stmt,
		const isl::set &	Subdomain
	)

Generate instructions that compute whether one instance of Set is executed.

Parameters

Stmt	The statement we generate code for.
Subdomain	A set in the space of `Stmt's` domain. Elements not in `Stmt's` domain are ignored.

Returns: An expression of type i1, generated into the current builder position, that evaluates to 1 if the executed instance is part of Set.

Definition at line 572 of file BlockGenerators.cpp.

References isl::set::apply(), assert, Builder, isl::ast_expr::copy(), polly::IslExprBuilder::create(), Domain, isl::ast_build::expr_from(), ExprBuilder, isl::map::from_union_map(), isl::ast_build::get_schedule(), polly::ScopStmt::getAstBuild(), polly::ScopStmt::getDomain(), isl::union_map::intersect_domain(), isl::union_map::is_empty(), isl::map::range(), isl::ast_build::restrict(), and polly::Value.

Referenced by generateConditionalExecution().

◆ canSyntheziseInStmt()

bool BlockGenerator::canSyntheziseInStmt	(	ScopStmt &	Stmt,
		Instruction *	Inst
	)

Helper to determine if Inst can be synthesized in Stmt.

Returns: false, iff Inst can be synthesized in Stmt.

Definition at line 334 of file BlockGenerators.cpp.

References polly::canSynthesize(), getLoopForStmt(), polly::ScopStmt::getParent(), polly::ScopStmt::getRegion(), polly::ScopStmt::isBlockStmt(), and SE.

Referenced by copyInstruction().

◆ copyBB() [1/2]

void BlockGenerator::copyBB	(	ScopStmt &	Stmt,
		BasicBlock *	BB,
		BasicBlock *	BBCopy,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS,
		isl_id_to_ast_expr *	NewAccesses
	)

Copy the given basic block.

Parameters

Stmt	The statement to code generate.
BB	The basic block to code generate.
BBCopy	The new basic block to generate code in.
BBMap	A mapping from old values to their new values in this block.
LTS	A map from old loops to new induction variables as SCEVs.
NewAccesses	A map from memory access ids to new ast expressions, which may contain new access expressions for certain memory accesses.

Definition at line 446 of file BlockGenerators.cpp.

References copyInstruction(), polly::ScopStmt::getEntryBlock(), polly::ScopStmt::getInstructions(), polly::ScopStmt::isBlockStmt(), and polly::ScopStmt::isRegionStmt().

◆ copyBB() [2/2]

BasicBlock * BlockGenerator::copyBB	(	ScopStmt &	Stmt,
		BasicBlock *	BB,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS,
		isl_id_to_ast_expr *	NewAccesses
	)

Copy the given basic block.

Parameters

Stmt	The statement to code generate.
BB	The basic block to code generate.
BBMap	A mapping from old values to their new values in this block.
LTS	A map from old loops to new induction variables as SCEVs.
NewAccesses	A map from memory access ids to new ast expressions, which may contain new access expressions for certain memory accesses.

Returns: The copy of the basic block.

Definition at line 419 of file BlockGenerators.cpp.

References Builder, copyBB(), generateBeginStmtTrace(), generateScalarLoads(), generateScalarStores(), and splitBB().

Referenced by copyBB(), polly::RegionGenerator::copyStmt(), and copyStmt().

◆ copyInstruction()

void BlockGenerator::copyInstruction	(	ScopStmt &	Stmt,
		Instruction *	Inst,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS,
		isl_id_to_ast_expr *	NewAccesses
	)

Copy a single Instruction.

This copies a single Instruction and updates references to old values with references to new values, as defined by GlobalMap and BBMap.

Parameters

Stmt	The statement to code generate.
Inst	The instruction to copy.
BBMap	A mapping from old values to their new values (for values recalculated within this basic block).
GlobalMap	A mapping from old values to their new values (for values recalculated in the new ScoP, but not within this basic block).
LTS	A mapping from loops virtual canonical induction variable to their new values (for values recalculated in the new ScoP, but not within this basic block).
NewAccesses	A map from memory access ids to new ast expressions, which may contain new access expressions for certain memory accesses.

Definition at line 340 of file BlockGenerators.cpp.

References canSyntheziseInStmt(), copyInstScalar(), copyPHIInstruction(), generateArrayLoad(), generateArrayStore(), polly::ScopStmt::getArrayAccessOrNULLFor(), polly::isIgnoredIntrinsic(), polly::PHI, and polly::Value.

Referenced by copyBB().

◆ copyInstScalar()

void BlockGenerator::copyInstScalar	(	ScopStmt &	Stmt,
		Instruction *	Inst,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS
	)

Definition at line 213 of file BlockGenerators.cpp.

References assert, Builder, getLoopForStmt(), getNewValue(), and polly::Value.

Referenced by copyInstruction(), and polly::RegionGenerator::copyStmt().

◆ copyPHIInstruction()

virtual void polly::BlockGenerator::copyPHIInstruction	(	ScopStmt &	,
		PHINode *	,
		ValueMapT &	,
		LoopToScevMapT &
	)

inlinevirtual

Copy a single PHI instruction.

The implementation in the BlockGenerator is trivial, however it allows subclasses to handle PHIs different.

Reimplemented in polly::RegionGenerator.

Definition at line 584 of file BlockGenerators.h.

Referenced by copyInstruction().

◆ copyStmt()

void BlockGenerator::copyStmt	(	ScopStmt &	Stmt,
		LoopToScevMapT &	LTS,
		isl_id_to_ast_expr *	NewAccesses
	)

Copy the basic block.

This copies the entire basic block and updates references to old values with references to new values, as defined by GlobalMap.

Parameters

Stmt	The block statement to code generate.
LTS	A map from old loops to new induction variables as SCEVs.
NewAccesses	A map from memory access ids to new ast expressions, which may contain new access expressions for certain memory accesses.

Definition at line 400 of file BlockGenerators.cpp.

References assert, copyBB(), polly::ScopStmt::getBasicBlock(), polly::ScopStmt::isBlockStmt(), and removeDeadInstructions().

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

◆ createExitPHINodeMerges()

void BlockGenerator::createExitPHINodeMerges ( Scop & S )

Create exit PHI node merges for PHI nodes with more than two edges from inside the scop.

For scops which have a PHI node in the exit block that has more than two incoming edges from inside the scop region, we require some special handling to understand which of the possible values will be passed to the PHI node from inside the optimized version of the scop. To do so ScopInfo models the possible incoming values as write accesses of the ScopStmts.

This function creates corresponding code to reload the computed outgoing value from the stack slot it has been stored into and to pass it on to the PHI node in the original exit block.

Parameters

S	The scop for which to generate the exiting PHI nodes.

Definition at line 919 of file BlockGenerators.cpp.

References assert, Builder, getOrCreateAlloca(), polly::PHI, and polly::Value.

Referenced by finalizeSCoP().

◆ createScalarFinalization()

void BlockGenerator::createScalarFinalization ( Scop & S )

Promote the values of demoted scalars after the SCoP.

If a scalar value was used outside the SCoP we need to promote the value stored in the memory cell allocated for that scalar and combine it with the original value in the non-optimized SCoP.

Definition at line 848 of file BlockGenerators.cpp.

References Builder, EscapeMap, SE, and polly::Value.

Referenced by finalizeSCoP().

◆ createScalarInitialization()

void BlockGenerator::createScalarInitialization ( Scop & S )

Initialize the memory of demoted scalars.

Parameters

S	The scop for which to generate the scalar initializers.

Definition at line 800 of file BlockGenerators.cpp.

References polly::Array, Builder, getOrCreateAlloca(), polly::PHI, StartBlock, and polly::Value.

Referenced by finalizeSCoP().

◆ finalizeSCoP()

void BlockGenerator::finalizeSCoP ( Scop & S )

Finalize the code generation for the SCoP S.

This will initialize and finalize the scalar variables we demoted during the code generation.

See also: createScalarInitialization(Scop &); createScalarFinalization(Region &)

Definition at line 994 of file BlockGenerators.cpp.

References createExitPHINodeMerges(), createScalarFinalization(), createScalarInitialization(), findOutsideUsers(), and invalidateScalarEvolution().

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

◆ findOutsideUsers()

void BlockGenerator::findOutsideUsers ( Scop & S )

Find scalar statements that have outside users.

We register these scalar values to later update subsequent scalar uses of these values to either use the newly computed value from within the scop (if the scop was executed) or the unchanged original code (if the run-time check failed).

Parameters

S	The scop for which to find the outside users.

Definition at line 895 of file BlockGenerators.cpp.

References polly::Array, and handleOutsideUsers().

Referenced by finalizeSCoP().

◆ freeScalarAlloc()

void polly::BlockGenerator::freeScalarAlloc ( ScopArrayInfo * Array )

inline

Remove a ScopArrayInfo's allocation from the ScalarMap.

This function allows to remove values from the ScalarMap. This is useful if the corresponding alloca instruction will be deleted (or moved into another module), as without removing these values the underlying AssertingVH will trigger due to us still keeping reference to this scalar.

Parameters

Array The array for which the alloca was generated.

Definition at line 120 of file BlockGenerators.h.

References polly::Array, and ScalarMap.

◆ generateArrayLoad()

Value * BlockGenerator::generateArrayLoad	(	ScopStmt &	Stmt,
		LoadInst *	load,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS,
		isl_id_to_ast_expr *	NewAccesses
	)

Parameters

NewAccesses A map from memory access ids to new ast expressions, which may contain new access expressions for certain memory accesses.

Definition at line 294 of file BlockGenerators.cpp.

References Builder, polly::RuntimeDebugBuilder::createCPUPrinter(), generateLocationAccessed(), GlobalMap, PollyDebugPrinting, and polly::Value.

Referenced by copyInstruction().

◆ generateArrayStore()

void BlockGenerator::generateArrayStore	(	ScopStmt &	Stmt,
		StoreInst *	store,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS,
		isl_id_to_ast_expr *	NewAccesses
	)

Parameters

NewAccesses A map from memory access ids to new ast expressions, which may contain new access expressions for certain memory accesses.

Definition at line 313 of file BlockGenerators.cpp.

References isl::map::domain(), generateConditionalExecution(), isl::id::get_name(), polly::MemoryAccess::getAccessRelation(), polly::ScopStmt::getArrayAccessFor(), and polly::MemoryAccess::getId().

Referenced by copyInstruction().

◆ generateBeginStmtTrace()

void BlockGenerator::generateBeginStmtTrace	(	ScopStmt &	Stmt,
		LoopToScevMapT &	LTS,
		ValueMapT &	BBMap
	)

When statement tracing is enabled, build the print instructions for printing the current statement instance.

The printed output looks like:

Stmt1(0)

If printing of scalars is enabled, it also appends the value of each scalar to the line:

Stmt1(0) %i=1 %sum=5

Parameters

Stmt	The statement we generate code for.
LTS	A mapping from loops virtual canonical induction variable to their new values.
BBMap	A mapping from old values to their new values in this block.

Definition at line 651 of file BlockGenerators.cpp.

References assert, isl::multi_pw_aff::at(), Builder, isl::ast_expr::copy(), polly::IslExprBuilder::create(), polly::RuntimeDebugBuilder::createCPUPrinter(), isl::multi_pw_aff::dim(), Domain, isl::ast_build::expr_from(), ExprBuilder, isl::pw_multi_aff::from_map(), isl::map::from_union_map(), isl::ast_build::get_schedule(), polly::ScopStmt::getAstBuild(), polly::ScopStmt::getBaseName(), polly::ScopStmt::getDomain(), getInstName(), getNewValue(), polly::ScopStmt::getParent(), polly::RuntimeDebugBuilder::getPrintableString(), polly::ScopStmt::insts(), isl::union_map::intersect_domain(), isl::map::is_empty(), isl::boolean::is_false(), polly::RuntimeDebugBuilder::isPrintable(), LI, isl::out, isl::map::range(), polly::rangeIslSize(), isl::ast_build::restrict(), isl::map::reverse(), TraceScalars(), TraceStmts(), and polly::Value.

Referenced by copyBB(), and polly::RegionGenerator::copyStmt().

◆ generateConditionalExecution()

void BlockGenerator::generateConditionalExecution	(	ScopStmt &	Stmt,
		const isl::set &	Subdomain,
		StringRef	Subject,
		const std::function< void()> &	GenThenFunc
	)

Generate code that executes in a subset of Stmt's domain.

Parameters

Stmt	The statement we generate code for.
Subdomain	The condition for some code to be executed.
Subject	A name for the code that is executed conditionally. Used to name new basic blocks and instructions.
GenThenFunc	Callback which generates the code to be executed when the current executed instance is in `Set`. The IRBuilder's position is moved to within the block that executes conditionally for this callback.

Definition at line 596 of file BlockGenerators.cpp.

References buildContainsCondition(), Builder, GenDT, GenLI, polly::Scop::getContext(), polly::ScopStmt::getDomain(), polly::ScopStmt::getParent(), isl::set::intersect_params(), isl::set::is_subset(), and polly::Value.

Referenced by generateArrayStore(), generateScalarStores(), and polly::RegionGenerator::generateScalarStores().

◆ generateLocationAccessed() [1/2]

Value * BlockGenerator::generateLocationAccessed	(	ScopStmt &	Stmt,
		Loop *	L,
		Value *	Pointer,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS,
		isl_id_to_ast_expr *	NewAccesses,
		__isl_take isl_id *	Id,
		Type *	ExpectedType
	)

Generate the operand address.

Parameters

Stmt	The statement to generate code for.
L	The innermost loop that surrounds the statement.
Pointer	If the access expression is not changed (ie. not found in `LTS`), use this Pointer from the original code instead.
BBMap	A mapping from old values to their new values.
LTS	A mapping from loops virtual canonical induction variable to their new values.
NewAccesses	Ahead-of-time generated access expressions.
Id	Identifier of the MemoryAccess to generate.
ExpectedType	The type the returned value should have.

Returns: The generated address.

Definition at line 261 of file BlockGenerators.cpp.

References assert, polly::IslExprBuilder::create(), ExprBuilder, getNewValue(), isl_ast_expr_address_of(), and polly::Value.

◆ generateLocationAccessed() [2/2]

Value * BlockGenerator::generateLocationAccessed	(	ScopStmt &	Stmt,
		MemAccInst	Inst,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS,
		isl_id_to_ast_expr *	NewAccesses
	)

Generate the operand address.

Parameters

NewAccesses A map from memory access ids to new ast expressions, which may contain new access expressions for certain memory accesses.

Definition at line 251 of file BlockGenerators.cpp.

References generateLocationAccessed(), polly::MemoryAccess::getAccessValue(), polly::ScopStmt::getArrayAccessFor(), polly::MemoryAccess::getId(), getLoopForStmt(), polly::MemAccInst::getPointerOperand(), polly::MemAccInst::isNull(), and isl::id::release().

Referenced by generateArrayLoad(), generateLocationAccessed(), and getImplicitAddress().

◆ generateScalarLoads()

void BlockGenerator::generateScalarLoads	(	ScopStmt &	Stmt,
		LoopToScevMapT &	LTS,
		ValueMapT &	BBMap,
		__isl_keep isl_id_to_ast_expr *	NewAccesses
	)

Generate reload of scalars demoted to memory and needed by Stmt.

Parameters

Stmt	The statement we generate code for.
LTS	A mapping from loops virtual canonical induction variable to their new values.
BBMap	A mapping from old values to their new values in this block.
NewAccesses	A map from memory access ids to new ast expressions.

Definition at line 550 of file BlockGenerators.cpp.

References assert, Builder, polly::Scop::getContext(), polly::ScopStmt::getDomain(), getImplicitAddress(), getLoopForStmt(), polly::ScopStmt::getParent(), and isl::set::intersect_params().

Referenced by copyBB(), and polly::RegionGenerator::copyStmt().

◆ generateScalarStores()

void BlockGenerator::generateScalarStores	(	ScopStmt &	Stmt,
		LoopToScevMapT &	LTS,
		ValueMapT &	BBMap,
		__isl_keep isl_id_to_ast_expr *	NewAccesses
	)

virtual

Generate the scalar stores for the given statement.

After the statement Stmt was copied all inner-SCoP scalar dependences starting in Stmt (hence all scalar write accesses in Stmt) need to be demoted to memory.

Parameters

Stmt	The statement we generate code for.
LTS	A mapping from loops virtual canonical induction variable to their new values (for values recalculated in the new ScoP, but not within this basic block)
BBMap	A mapping from old values to their new values in this block.
NewAccesses	A map from memory access ids to new ast expressions.

Reimplemented in polly::RegionGenerator.

Definition at line 744 of file BlockGenerators.cpp.

References assert, Builder, DT, generateConditionalExecution(), polly::ScopStmt::getBasicBlock(), getImplicitAddress(), getLoopForStmt(), getNewValue(), polly::ScopStmt::isBlockStmt(), and LI.

Referenced by copyBB().

◆ getImplicitAddress()

Value * BlockGenerator::getImplicitAddress	(	MemoryAccess &	Access,
		Loop *	L,
		LoopToScevMapT &	LTS,
		ValueMapT &	BBMap,
		__isl_keep isl_id_to_ast_expr *	NewAccesses
	)

Generate the pointer value that is accesses by Access.

For write accesses, generate the target address. For read accesses, generate the source address. The access can be either an array access or a scalar access. In the first case, the returned address will point to an element into that array. In the scalar case, an alloca is used. If a new AccessRelation is set for the MemoryAccess, the new relation will be used.

Parameters

Access	The access to generate a pointer for.
L	The innermost loop that surrounds the statement.
LTS	A mapping from loops virtual canonical induction variable to their new values.
BBMap	A mapping from old values to their new values.
NewAccesses	A map from memory access ids to new ast expressions.

Returns: The generated address.

Definition at line 278 of file BlockGenerators.cpp.

References generateLocationAccessed(), polly::MemoryAccess::getAccessValue(), polly::MemoryAccess::getId(), getOrCreateAlloca(), polly::MemoryAccess::getStatement(), polly::MemoryAccess::isLatestArrayKind(), and isl::id::release().

Referenced by generateScalarLoads(), and generateScalarStores().

◆ getLoopForStmt()

Loop * BlockGenerator::getLoopForStmt ( const ScopStmt & Stmt ) const

Get the innermost loop that surrounds the statement Stmt.

Definition at line 289 of file BlockGenerators.cpp.

References polly::ScopStmt::getEntryBlock(), and LI.

Referenced by polly::RegionGenerator::addOperandToPHI(), canSyntheziseInStmt(), copyInstScalar(), generateLocationAccessed(), generateScalarLoads(), and generateScalarStores().

◆ getNewValue()

Value * BlockGenerator::getNewValue	(	ScopStmt &	Stmt,
		Value *	Old,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS,
		Loop *	L
	)		const

Get the new version of a value.

Given an old value, we first check if a new version of this value is available in the BBMap or GlobalMap. In case it is not and the value can be recomputed using SCEV, we do so. If we can not recompute a value using SCEV, but we understand that the value is constant within the scop, we return the old value. If the value can still not be derived, this function will assert.

Parameters

Stmt	The statement to code generate.
Old	The old Value.
BBMap	A mapping from old values to their new values (for values recalculated within this basic block).
LTS	A mapping from loops virtual canonical induction variable to their new values (for values recalculated in the new ScoP, but not within this basic block).
L	The loop that surrounded the instruction that referenced this value in the original code. This loop is used to evaluate the scalar evolution at the right scope.

Returns: o The old value, if it is still valid. o The new value, if available. o NULL, if no value is found.

Definition at line 96 of file BlockGenerators.cpp.

References assert, polly::VirtualUse::Block, Builder, polly::VirtualUse::Constant, polly::VirtualUse::create(), GlobalMap, polly::VirtualUse::Hoisted, polly::VirtualUse::Inter, polly::VirtualUse::Intra, polly::VirtualUse::ReadOnly, polly::VirtualUse::Synthesizable, trySynthesizeNewValue(), and polly::Value.

Referenced by polly::RegionGenerator::addOperandToPHI(), polly::RegionGenerator::buildExitPHI(), copyInstScalar(), generateBeginStmtTrace(), generateLocationAccessed(), generateScalarStores(), and polly::RegionGenerator::getExitScalar().

◆ getOrCreateAlloca() [1/2]

Value * BlockGenerator::getOrCreateAlloca ( const MemoryAccess & Access )

Return the alloca for Access.

If no alloca was mapped for Access a new one is created.

Parameters

Access The memory access for which to generate the alloca.

Returns: The alloca for Access or a replacement value taken from GlobalMap.

Definition at line 462 of file BlockGenerators.cpp.

References assert, polly::MemoryAccess::getLatestScopArrayInfo(), getOrCreateAlloca(), polly::MemoryAccess::isLatestArrayKind(), and polly::Value.

Referenced by createExitPHINodeMerges(), createScalarInitialization(), getImplicitAddress(), getOrCreateAlloca(), and handleOutsideUsers().

◆ getOrCreateAlloca() [2/2]

Value * BlockGenerator::getOrCreateAlloca ( const ScopArrayInfo * Array )

Return the alloca for Array.

If no alloca was mapped for Array a new one is created.

Parameters

Array The array for which to generate the alloca.

Returns: The alloca for Array or a replacement value taken from GlobalMap.

Definition at line 468 of file BlockGenerators.cpp.

References polly::Array, assert, Builder, GlobalMap, ScalarMap, and polly::Value.

◆ handleOutsideUsers()

void BlockGenerator::handleOutsideUsers	(	const Scop &	S,
		ScopArrayInfo *	Array
	)

Handle users of Array outside the SCoP.

Parameters

S	The current SCoP.
Inst	The ScopArrayInfo to handle.

Definition at line 516 of file BlockGenerators.cpp.

References polly::Array, EscapeMap, and getOrCreateAlloca().

Referenced by findOutsideUsers().

◆ invalidateScalarEvolution()

void BlockGenerator::invalidateScalarEvolution ( Scop & S )

Invalidate the scalar evolution expressions for a scop.

This function invalidates the scalar evolution results for all instructions that are part of a given scop, and the loops surrounding the users of merge blocks. This is necessary to ensure that later scops do not obtain scalar evolution expressions that reference values that earlier dominated the later scop, but have been moved in the conditional part of an earlier scop and consequently do not any more dominate the later scop.

Parameters

S	The scop to invalidate.

Definition at line 967 of file BlockGenerators.cpp.

References EscapeMap, LI, and SE.

Referenced by finalizeSCoP().

◆ removeDeadInstructions()

void BlockGenerator::removeDeadInstructions	(	BasicBlock *	BB,
		ValueMapT &	BBMap
	)

Remove dead instructions generated for BB.

Parameters

BB	The basic block code for which code has been generated.
BBMap	A local map from old to new instructions.

Definition at line 382 of file BlockGenerators.cpp.

References Builder.

Referenced by copyStmt().

◆ splitBB()

BasicBlock * BlockGenerator::splitBB ( BasicBlock * BB )

Split BB to create a new one we can use to clone BB in.

Definition at line 412 of file BlockGenerators.cpp.

References Builder, GenDT, and GenLI.

Referenced by copyBB(), and polly::RegionGenerator::copyStmt().

◆ switchGeneratedFunc()

void BlockGenerator::switchGeneratedFunc	(	Function *	GenFn,
		DominatorTree *	GenDT,
		LoopInfo *	GenLI,
		ScalarEvolution *	GenSE
	)

Change the function that code is emitted into.

Definition at line 435 of file BlockGenerators.cpp.

References assert, GenDT, GenLI, and GenSE.

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

◆ trySynthesizeNewValue()

Value * BlockGenerator::trySynthesizeNewValue	(	ScopStmt &	Stmt,
		Value *	Old,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS,
		Loop *	L
	)		const

Try to synthesize a new value.

Given an old value, we try to synthesize it in a new context from its original SCEV expression. We start from the original SCEV expression, then replace outdated parameter and loop references, and finally expand it to code that computes this updated expression.

Parameters

Stmt	The statement to code generate
Old	The old Value
BBMap	A mapping from old values to their new values (for values recalculated within this basic block)
LTS	A mapping from loops virtual canonical induction variable to their new values (for values recalculated in the new ScoP, but not within this basic block)
L	The loop that surrounded the instruction that referenced this value in the original code. This loop is used to evaluate the scalar evolution at the right scope.

Returns: o A newly synthesized value. o NULL, if synthesizing the value failed.

Definition at line 64 of file BlockGenerators.cpp.

References assert, Builder, polly::expandCodeFor(), GenSE, polly::ScopStmt::getParent(), GlobalMap, SE, StartBlock, and polly::Value.

Referenced by getNewValue().

Member Data Documentation

◆ Builder

PollyIRBuilder& polly::BlockGenerator::Builder

protected

◆ DT

DominatorTree& polly::BlockGenerator::DT

protected

The dominator tree of this function.

Definition at line 163 of file BlockGenerators.h.

Referenced by polly::RegionGenerator::copyStmt(), generateScalarStores(), and polly::RegionGenerator::repairDominance().

◆ EscapeMap

EscapeUsersAllocaMapTy& polly::BlockGenerator::EscapeMap

Map from instructions to their escape users as well as the alloca.

Definition at line 293 of file BlockGenerators.h.

Referenced by createScalarFinalization(), handleOutsideUsers(), and invalidateScalarEvolution().

◆ ExprBuilder

IslExprBuilder* polly::BlockGenerator::ExprBuilder

protected

Definition at line 160 of file BlockGenerators.h.

Referenced by buildContainsCondition(), generateBeginStmtTrace(), and generateLocationAccessed().

◆ GenDT

DominatorTree* polly::BlockGenerator::GenDT

protected

Relates to the region where the code is emitted into.

Definition at line 167 of file BlockGenerators.h.

Referenced by generateConditionalExecution(), splitBB(), and switchGeneratedFunc().

◆ GenLI

LoopInfo* polly::BlockGenerator::GenLI

protected

Definition at line 168 of file BlockGenerators.h.

Referenced by generateConditionalExecution(), splitBB(), and switchGeneratedFunc().

◆ GenSE

ScalarEvolution* polly::BlockGenerator::GenSE

protected

Definition at line 169 of file BlockGenerators.h.

Referenced by switchGeneratedFunc(), and trySynthesizeNewValue().

◆ GlobalMap

ValueMapT& polly::BlockGenerator::GlobalMap

A map from llvm::Values referenced in the old code to a new set of llvm::Values, which is used to replace these old values during code generation.

Definition at line 298 of file BlockGenerators.h.

Referenced by generateArrayLoad(), getNewValue(), getOrCreateAlloca(), and trySynthesizeNewValue().

◆ LI

LoopInfo& polly::BlockGenerator::LI

protected

Definition at line 158 of file BlockGenerators.h.

Referenced by polly::RegionGenerator::copyStmt(), generateBeginStmtTrace(), generateScalarStores(), polly::RegionGenerator::getExitScalar(), getLoopForStmt(), and invalidateScalarEvolution().

◆ ScalarMap

AllocaMapTy& polly::BlockGenerator::ScalarMap

Map to resolve scalar dependences for PHI operands and scalars.

When translating code that contains scalar dependences as they result from inter-block scalar dependences (including the use of data carrying PHI nodes), we do not directly regenerate in-register SSA code, but instead allocate some stack memory through which these scalar values are passed. Only a later pass of -mem2reg will then (re)introduce in-register computations.

To keep track of the memory location(s) used to store the data computed by a given SSA instruction, we use the map 'ScalarMap'. ScalarMap maps a given ScopArrayInfo to the junk of stack allocated memory, that is used for code generation.

Up to two different ScopArrayInfo objects are associated with each llvm::Value:

MemoryType::Value objects are used for normal scalar dependences that go from a scalar definition to its use. Such dependences are lowered by directly writing the value an instruction computes into the corresponding chunk of memory and reading it back from this chunk of memory right before every use of this original scalar value. The memory allocations for MemoryType::Value objects end with '.s2a'.

MemoryType::PHI (and MemoryType::ExitPHI) objects are used to model PHI nodes. For each PHI nodes we introduce, besides the Array of type MemoryType::Value, a second chunk of memory into which we write at the end of each basic block preceding the PHI instruction the value passed through this basic block. At the place where the PHI node is executed, we replace the PHI node with a load from the corresponding MemoryType::PHI memory location. The memory allocations for MemoryType::PHI end with '.phiops'.

Example:

                         Input C Code
                         ============

            S1:      x1 = ...
                     for (i=0...N) {
            S2:           x2 = phi(x1, add)
            S3:           add = x2 + 42;
                     }
            S4:      print(x1)
                     print(x2)
                     print(add)


   Unmodified IR                         IR After expansion
   =============                         ==================

S1: x1 = ... S1: x1 = ... x1.s2a = s1 x2.phiops = s1 | | | <–<–<–<–< | <–<–<–<–< | / \ | / \ . V V \ V V \ . S2: x2 = phi (x1, add) | S2: x2 = x2.phiops | | x2.s2a = x2 | | | S3: add = x2 + 42 | S3: add = x2 + 42 | | add.s2a = add | | x2.phiops = add | | \ / | \ / | \ / | \ / | >-->-->-->--> | >-->-->-->--> V V

                        S4:    x1 = x1.s2a

S4: ... = x1 ... = x1 x2 = x2.s2a ... = x2 ... = x2 add = add.s2a ... = add ... = add

ScalarMap = { x1:Value -> x1.s2a, x2:Value -> x2.s2a, add:Value -> add.s2a, x2:PHI -> x2.phiops }

??? Why does a PHI-node require two memory chunks ???

One may wonder why a PHI node requires two memory chunks and not just all data is stored in a single location. The following example tries to store all data in .s2a and drops the .phiops location:

S1:    x1 = ...
       x1.s2a = s1
       x2.s2a = s1             // use .s2a instead of .phiops
         |
         |   <--<--<--<--<
         | /              \    .
         V V               \   .
S2:    x2 = x2.s2a          |  // value is same as above, but read
                            |  // from .s2a
                            |
       x2.s2a = x2          |  // store into .s2a as normal
                            |
S3:    add = x2 + 42        |
       add.s2a = add        |
       x2.s2a = add         |  // use s2a instead of .phiops
         | \               /   // !!! This is wrong, as x2.s2a now
         |   >-->-->-->-->     // contains add instead of x2.
         V

S4:    x1 = x1.s2a
       ... = x1
       x2 = x2.s2a             // !!! We now read 'add' instead of
       ... = x2                // 'x2'
       add = add.s2a
       ... = add

As visible in the example, the SSA value of the PHI node may still be needed after the basic block, which could conceptually branch to the PHI node, has been run and has overwritten the PHI's old value. Hence, a single memory location is not enough to code-generate a PHI node.

Memory locations used for the special PHI node modeling.

Definition at line 290 of file BlockGenerators.h.

Referenced by freeScalarAlloc(), and getOrCreateAlloca().

◆ SE

ScalarEvolution& polly::BlockGenerator::SE

protected

Definition at line 159 of file BlockGenerators.h.

Referenced by canSyntheziseInStmt(), polly::RegionGenerator::copyStmt(), createScalarFinalization(), invalidateScalarEvolution(), and trySynthesizeNewValue().

◆ StartBlock

BasicBlock* polly::BlockGenerator::StartBlock

The first basic block after the RTC.

Definition at line 301 of file BlockGenerators.h.

Referenced by createScalarInitialization(), and trySynthesizeNewValue().

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Public Attributes

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ AllocaMapTy

◆ EscapeUsersAllocaMapTy

◆ EscapeUserVectorTy

◆ VectorValueMapT

Constructor & Destructor Documentation

◆ BlockGenerator() [1/2]

◆ ~BlockGenerator()

◆ BlockGenerator() [2/2]

Member Function Documentation

◆ buildContainsCondition()

◆ canSyntheziseInStmt()

◆ copyBB() [1/2]

◆ copyBB() [2/2]

◆ copyInstruction()

◆ copyInstScalar()

◆ copyPHIInstruction()

◆ copyStmt()

◆ createExitPHINodeMerges()

◆ createScalarFinalization()

◆ createScalarInitialization()

◆ finalizeSCoP()

◆ findOutsideUsers()

◆ freeScalarAlloc()

◆ generateArrayLoad()

◆ generateArrayStore()

◆ generateBeginStmtTrace()

◆ generateConditionalExecution()

◆ generateLocationAccessed() [1/2]

◆ generateLocationAccessed() [2/2]

◆ generateScalarLoads()

◆ generateScalarStores()

◆ getImplicitAddress()

◆ getLoopForStmt()

◆ getNewValue()

◆ getOrCreateAlloca() [1/2]

◆ getOrCreateAlloca() [2/2]

◆ handleOutsideUsers()

◆ invalidateScalarEvolution()

◆ removeDeadInstructions()

◆ splitBB()

◆ switchGeneratedFunc()

◆ trySynthesizeNewValue()

Member Data Documentation

◆ Builder

◆ DT

◆ EscapeMap

◆ ExprBuilder

◆ GenDT

◆ GenLI

◆ GenSE

◆ GlobalMap

◆ LI

◆ ScalarMap

◆ SE

◆ StartBlock