Generator for new versions of polyhedral region statements. More...

#include <BlockGenerators.h>

Inheritance diagram for polly::RegionGenerator:

Public Member Functions
	RegionGenerator (BlockGenerator &BlockGen)
	Create a generator for regions.

virtual	~RegionGenerator ()

void	copyStmt (ScopStmt &Stmt, LoopToScevMapT &LTS, __isl_keep isl_id_to_ast_expr *IdToAstExp)
	Copy the region statement `Stmt`.

Private Types
using	PHINodePairTy = std::pair< PHINode , PHINode >
	Mapping to remember PHI nodes that still need incoming values.

Private Types inherited from polly::BlockGenerator
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.

Private Member Functions
BasicBlock *	repairDominance (BasicBlock BB, BasicBlock BBCopy)
	Repair the dominance tree after we created a copy block for `BB`.

void	addOperandToPHI (ScopStmt &Stmt, PHINode PHI, PHINode PHICopy, BasicBlock *IncomingBB, LoopToScevMapT &LTS)
	Add the new operand from the copy of `IncomingBB` to `PHICopy`.

PHINode *	buildExitPHI (MemoryAccess MA, LoopToScevMapT &LTS, ValueMapT &BBMap, Loop L)
	Create a PHI that combines the incoming values from all incoming blocks that are in the subregion.

Value *	getExitScalar (MemoryAccess *MA, LoopToScevMapT &LTS, ValueMapT &BBMap)

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

void	copyPHIInstruction (ScopStmt &Stmt, PHINode *Inst, ValueMapT &BBMap, LoopToScevMapT &LTS) override
	Copy a single PHI instruction.

Private Member Functions inherited from polly::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.

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.

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.

Private Attributes
DenseMap< BasicBlock , BasicBlock >	StartBlockMap
	A map from old to the first new block in the region, that was created to model the old basic block.

DenseMap< BasicBlock , BasicBlock >	EndBlockMap
	A map from old to the last new block in the region, that was created to model the old basic block.

DenseMap< BasicBlock *, ValueMapT >	RegionMaps
	The "BBMaps" for the whole region (one for each block).

DenseMap< BasicBlock *, SmallVector< PHINodePairTy, 4 > >	IncompletePHINodeMap

Private Attributes inherited from polly::BlockGenerator
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

Generator for new versions of polyhedral region statements.

Definition at line 626 of file BlockGenerators.h.

Member Typedef Documentation

◆ PHINodePairTy

using polly::RegionGenerator::PHINodePairTy = std::pair<PHINode *, PHINode *>

private

Mapping to remember PHI nodes that still need incoming values.

Definition at line 661 of file BlockGenerators.h.

Constructor & Destructor Documentation

◆ RegionGenerator()

polly::RegionGenerator::RegionGenerator ( BlockGenerator & BlockGen )

inline

Create a generator for regions.

Parameters

BlockGen A generator for basic blocks.

Definition at line 631 of file BlockGenerators.h.

◆ ~RegionGenerator()

virtual polly::RegionGenerator::~RegionGenerator ( )

inlinevirtual

Definition at line 633 of file BlockGenerators.h.

Member Function Documentation

◆ addOperandToPHI()

void RegionGenerator::addOperandToPHI	(	ScopStmt &	Stmt,
		PHINode *	PHI,
		PHINode *	PHICopy,
		BasicBlock *	IncomingBB,
		LoopToScevMapT &	LTS
	)

private

Add the new operand from the copy of IncomingBB to PHICopy.

PHI nodes, which may have (multiple) edges that enter from outside the non-affine subregion and even from outside the scop, are code generated as follows:

Original

Region: A-> exit NonAffine Stmt: nonaffB -> D (includes nonaffB, nonaffC)

pre: val = add i64 1, 1

A: br label nonaff

nonaffB: phi = phi i64 [val, A], [valC, nonAffC], [valD, D] cmp = <nonaff> br i1 cmp, label C, label nonaffC

nonaffC: valC = add i64 1, 1 br i1 undef, label D, label nonaffB

D: valD = ... exit_cond = <loopexit> br i1 exit_cond, label nonaffB, label exit

exit: ...

start and C enter from outside the non-affine region.
nonaffC enters from within the non-affine region.

New

polly.A: store i64 val, i64* phi.phiops br label polly.nonaffA.entry

polly.nonaffB.entry: phi.phiops.reload = load i64, i64* phi.phiops br label nonaffB

polly.nonaffB: polly.phi = [phi.phiops.reload, nonaffB.entry], [p.valC, polly.nonaffC]

polly.nonaffC: p.valC = add i64 1, 1 br i1 undef, label polly.D, label polly.nonaffB

polly.D: p.valD = ... store i64 p.valD, i64* phi.phiops p.exit_cond = <loopexit> br i1 p.exit_cond, label polly.nonaffB, label exit

Values that enter the PHI from outside the non-affine region are stored into the stack slot phi.phiops by statements polly.A and polly.D and reloaded in polly.nonaffB.entry, a basic block generated before the actual non-affine region.

When generating the PHI node of the non-affine region in polly.nonaffB, incoming edges from outside the region are combined into a single branch from polly.nonaffB.entry which has as incoming value the value reloaded from the phi.phiops stack slot. Incoming edges from within the region refer to the copied instructions (p.valC) and basic blocks (polly.nonaffC) of the non-affine region.

Parameters

Stmt	The statement to code generate.
PHI	The original PHI we copy.
PHICopy	The copy of `PHI`.
IncomingBB	An incoming block of `PHI`.
LTS	A map from old loops to new induction variables as SCEVs.

Definition at line 1333 of file BlockGenerators.cpp.

References assert, polly::BlockGenerator::Builder, EndBlockMap, polly::BlockGenerator::getLoopForStmt(), polly::BlockGenerator::getNewValue(), IncompletePHINodeMap, polly::PHI, RegionMaps, polly::ScopStmt::represents(), StartBlockMap, and polly::Value.

Referenced by copyPHIInstruction(), and copyStmt().

◆ buildExitPHI()

PHINode * RegionGenerator::buildExitPHI	(	MemoryAccess *	MA,
		LoopToScevMapT &	LTS,
		ValueMapT &	BBMap,
		Loop *	L
	)

private

Create a PHI that combines the incoming values from all incoming blocks that are in the subregion.

PHIs in the subregion's exit block can have incoming edges from within and outside the subregion. This function combines the incoming values from within the subregion to appear as if there is only one incoming edge from the subregion (an additional exit block is created by RegionGenerator). This is to avoid that a value is written to the .phiops location without leaving the subregion because the exiting block as an edge back into the subregion.

Parameters

MA	The WRITE of MemoryKind::PHI/MemoryKindExitPHI for a PHI in the subregion's exit block.
LTS	Virtual induction variable mapping.
BBMap	A mapping from old values to their new values in this block.
L	Loop surrounding this region statement.

Returns: The constructed PHI node.

Definition at line 1217 of file BlockGenerators.cpp.

References assert, polly::BlockGenerator::Builder, EndBlockMap, polly::MemoryAccess::getAccessInstruction(), polly::MemoryAccess::getIncoming(), polly::BlockGenerator::getNewValue(), polly::ScopStmt::getRegion(), polly::MemoryAccess::getStatement(), RegionMaps, StartBlockMap, and polly::Value.

Referenced by getExitScalar().

◆ copyPHIInstruction()

void RegionGenerator::copyPHIInstruction	(	ScopStmt &	Stmt,
		PHINode *	Inst,
		ValueMapT &	BBMap,
		LoopToScevMapT &	LTS
	)

overrideprivatevirtual

Copy a single PHI instruction.

This copies a single PHI 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.
PHI	The PHI instruction to copy.
BBMap	A mapping from old values to their new values (for values recalculated within this basic block).
LTS	A map from old loops to new induction variables as SCEVs.

Reimplemented from polly::BlockGenerator.

Definition at line 1381 of file BlockGenerators.cpp.

References addOperandToPHI(), polly::BlockGenerator::Builder, and polly::PHI.

◆ copyStmt()

void RegionGenerator::copyStmt	(	ScopStmt &	Stmt,
		LoopToScevMapT &	LTS,
		__isl_keep isl_id_to_ast_expr *	IdToAstExp
	)

Copy the region statement Stmt.

This copies the entire region represented by Stmt and updates references to old values with references to new values, as defined by GlobalMap.

Parameters

Stmt	The statement to code generate.
LTS	A map from old loops to new induction variables as SCEVs.

Definition at line 1052 of file BlockGenerators.cpp.

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

◆ generateScalarStores()

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

overrideprivatevirtual

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.
LTS	A mapping from loops virtual canonical induction variable to their new values.

Reimplemented from polly::BlockGenerator.

Definition at line 1285 of file BlockGenerators.cpp.

References assert, polly::BlockGenerator::generateConditionalExecution(), getExitScalar(), polly::ScopStmt::getRegion(), and polly::Value.

Referenced by copyStmt().

◆ getExitScalar()

Value * RegionGenerator::getExitScalar	(	MemoryAccess *	MA,
		LoopToScevMapT &	LTS,
		ValueMapT &	BBMap
	)

private

Parameters

Return	the new value of a scalar write, creating a PHINode if necessary.
MA	A scalar WRITE MemoryAccess.
LTS	Virtual induction variable mapping.
BBMap	A mapping from old values to their new values in this block.

Returns: The effective value of MA's written value when leaving the subregion.

See also: buildExitPHI

Definition at line 1258 of file BlockGenerators.cpp.

References assert, buildExitPHI(), polly::MemoryAccess::getAccessValue(), polly::MemoryAccess::getIncoming(), polly::BlockGenerator::getNewValue(), polly::ScopStmt::getRegion(), polly::MemoryAccess::getStatement(), polly::MemoryAccess::isAnyPHIKind(), polly::BlockGenerator::LI, and polly::Value.

Referenced by generateScalarStores().

◆ repairDominance()

BasicBlock * RegionGenerator::repairDominance	(	BasicBlock *	BB,
		BasicBlock *	BBCopy
	)

private

Repair the dominance tree after we created a copy block for BB.

Returns: The immediate dominator in the DT for BBCopy if in the region.

Definition at line 996 of file BlockGenerators.cpp.

References polly::BlockGenerator::DT, EndBlockMap, and StartBlockMap.

Referenced by copyStmt().

Member Data Documentation

◆ EndBlockMap

DenseMap<BasicBlock *, BasicBlock *> polly::RegionGenerator::EndBlockMap

private

A map from old to the last new block in the region, that was created to model the old basic block.

Definition at line 653 of file BlockGenerators.h.

Referenced by addOperandToPHI(), buildExitPHI(), copyStmt(), and repairDominance().

◆ IncompletePHINodeMap

DenseMap<BasicBlock *, SmallVector<PHINodePairTy, 4> > polly::RegionGenerator::IncompletePHINodeMap

private

Definition at line 662 of file BlockGenerators.h.

Referenced by addOperandToPHI(), and copyStmt().

◆ RegionMaps

DenseMap<BasicBlock *, ValueMapT> polly::RegionGenerator::RegionMaps

private

The "BBMaps" for the whole region (one for each block).

In case a basic block is code generated to multiple basic blocks (e.g., for partial writes), the StartBasic is used as index for the RegionMap.

Definition at line 658 of file BlockGenerators.h.

Referenced by addOperandToPHI(), buildExitPHI(), and copyStmt().

◆ StartBlockMap

DenseMap<BasicBlock *, BasicBlock *> polly::RegionGenerator::StartBlockMap

private

A map from old to the first new block in the region, that was created to model the old basic block.

Definition at line 649 of file BlockGenerators.h.

Referenced by addOperandToPHI(), buildExitPHI(), copyStmt(), and repairDominance().

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

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ PHINodePairTy

Constructor & Destructor Documentation

◆ RegionGenerator()

◆ ~RegionGenerator()

Member Function Documentation

◆ addOperandToPHI()

Original

New

◆ buildExitPHI()

◆ copyPHIInstruction()

◆ copyStmt()

◆ generateScalarStores()

◆ getExitScalar()

◆ repairDominance()

Member Data Documentation

◆ EndBlockMap

◆ IncompletePHINodeMap

◆ RegionMaps

◆ StartBlockMap