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

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

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.

Protected Attributes
PollyIRBuilder &	Builder

LoopInfo &	LI

ScalarEvolution &	SE

IslExprBuilder *	ExprBuilder

DominatorTree &	DT
	The dominator tree of this function.

BasicBlock *	EntryBB
	The entry block of the current function.

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.

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
	)

protected

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

protected

Helper to determine if Inst can be synthesized in Stmt.

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

Definition at line 333 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
	)

protected

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 434 of file BlockGenerators.cpp.

References copyInstruction(), EntryBB, 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
	)

protected

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

protected

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

protected

Definition at line 214 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 &
	)

inlineprotectedvirtual

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 575 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 399 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 )

protected

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 913 of file BlockGenerators.cpp.

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

Referenced by finalizeSCoP().

◆ createScalarFinalization()

void BlockGenerator::createScalarFinalization ( Scop & S )

protected

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 842 of file BlockGenerators.cpp.

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

Referenced by finalizeSCoP().

◆ createScalarInitialization()

void BlockGenerator::createScalarInitialization ( Scop & S )

protected

Initialize the memory of demoted scalars.

Parameters

S	The scop for which to generate the scalar initializers.

Definition at line 794 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 988 of file BlockGenerators.cpp.

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

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

◆ findOutsideUsers()

void BlockGenerator::findOutsideUsers ( Scop & S )

protected

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

protected

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

protected

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

protected

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

protected

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 590 of file BlockGenerators.cpp.

References buildContainsCondition(), Builder, DT, polly::Scop::getContext(), polly::ScopStmt::getDomain(), polly::ScopStmt::getParent(), isl::set::intersect_params(), isl::set::is_subset(), LI, 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
	)

protected

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

protected

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

protected

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 540 of file BlockGenerators.cpp.

References assert, Builder, DT, 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
	)

protectedvirtual

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

protected

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 277 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

protected

Get the innermost loop that surrounds the statement Stmt.

Definition at line 288 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

protected

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 97 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 452 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 458 of file BlockGenerators.cpp.

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

◆ handleOutsideUsers()

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

protected

Handle users of Array outside the SCoP.

Parameters

S	The current SCoP.
Inst	The ScopArrayInfo to handle.

Definition at line 506 of file BlockGenerators.cpp.

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

Referenced by findOutsideUsers().

◆ invalidateScalarEvolution()

void BlockGenerator::invalidateScalarEvolution ( Scop & S )

protected

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 961 of file BlockGenerators.cpp.

References EscapeMap, LI, and SE.

Referenced by finalizeSCoP().

◆ removeDeadInstructions()

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

protected

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 381 of file BlockGenerators.cpp.

References Builder.

Referenced by copyStmt().

◆ splitBB()

BasicBlock * BlockGenerator::splitBB ( BasicBlock * BB )

protected

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

Definition at line 411 of file BlockGenerators.cpp.

References Builder, DT, and LI.

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

◆ trySynthesizeNewValue()

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

protected

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(), 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(), generateConditionalExecution(), generateScalarLoads(), generateScalarStores(), polly::RegionGenerator::repairDominance(), and splitBB().

◆ EntryBB

BasicBlock* polly::BlockGenerator::EntryBB

protected

The entry block of the current function.

Definition at line 166 of file BlockGenerators.h.

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

◆ EscapeMap

EscapeUsersAllocaMapTy& polly::BlockGenerator::EscapeMap

protected

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

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

◆ GlobalMap

ValueMapT& polly::BlockGenerator::GlobalMap

protected

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 293 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(), generateConditionalExecution(), generateScalarStores(), polly::RegionGenerator::getExitScalar(), getLoopForStmt(), invalidateScalarEvolution(), and splitBB().

◆ ScalarMap

AllocaMapTy& polly::BlockGenerator::ScalarMap

protected

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 285 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

protected

The first basic block after the RTC.

Definition at line 296 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

Protected Member Functions

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

◆ trySynthesizeNewValue()

Member Data Documentation

◆ Builder

◆ DT

◆ EntryBB

◆ EscapeMap

◆ ExprBuilder

◆ GlobalMap

◆ LI

◆ ScalarMap

◆ SE

◆ StartBlock