ZoneAlgo.cpp File Reference

#include "polly/ZoneAlgo.h"
#include "polly/ScopInfo.h"
#include "polly/Support/GICHelper.h"
#include "polly/Support/ISLTools.h"
#include "polly/Support/VirtualInstruction.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/raw_ostream.h"
#include "polly/Support/PollyDebug.h"

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "polly-zone"

Functions
	STATISTIC (NumIncompatibleArrays, "Number of not zone-analyzable arrays")
	STATISTIC (NumCompatibleArrays, "Number of zone-analyzable arrays")
	STATISTIC (NumRecursivePHIs, "Number of recursive PHIs")
	STATISTIC (NumNormalizablePHIs, "Number of normalizable PHIs")
	STATISTIC (NumPHINormialization, "Number of PHI executed normalizations")
static isl::union_map	computeReachingDefinition (isl::union_map Schedule, isl::union_map Writes, bool InclDef, bool InclRedef)
static isl::union_map	computeScalarReachingDefinition (isl::union_map Schedule, isl::union_set Writes, bool InclDef, bool InclRedef)
	Compute the reaching definition of a scalar.
static isl::map	computeScalarReachingDefinition (isl::union_map Schedule, isl::set Writes, bool InclDef, bool InclRedef)
	Compute the reaching definition of a scalar.
static isl::map	makeUnknownForDomain (isl::set Domain)
	Create a domain-to-unknown value mapping.
static bool	isMapToUnknown (const isl::map &Map)
	Return whether Map maps to an unknown value.
static bool	onlySameValueWrites (ScopStmt *Stmt)
	Check if all stores in Stmt store the very same value.
static bool	isInsideLoop (Loop *OuterLoop, Loop *InnerLoop)
	Is InnerLoop nested inside OuterLoop?
static bool	isRecursivePHI (const PHINode *PHI)
	Return whether PHI refers (also transitively through other PHIs) to itself.
static isl::union_map	normalizeValInst (isl::union_map Input, const DenseSet< PHINode * > &ComputedPHIs, isl::union_map NormalizeMap)
	Remove all computed PHIs out of Input and replace by their incoming value.

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "polly-zone"

Definition at line 160 of file ZoneAlgo.cpp.

Function Documentation

computeReachingDefinition()

static isl::union_map computeReachingDefinition ( isl::union_map  Schedule, isl::union_map  Writes, bool  InclDef, bool  InclRedef  )

static

Definition at line 171 of file ZoneAlgo.cpp.

References polly::computeReachingWrite().

Referenced by polly::ZoneAlgorithm::computeCommon(), and computeScalarReachingDefinition().

computeScalarReachingDefinition() [1/2]

static isl::map computeScalarReachingDefinition ( isl::union_map  Schedule, isl::set  Writes, bool  InclDef, bool  InclRedef  )

static

Compute the reaching definition of a scalar.

This overload accepts only a single writing statement as an isl_map, consequently the result also is only a single isl_map.

Parameters

Schedule	{ DomainWrite[] -> Scatter[] }
Writes	{ DomainWrite[] }
InclDef	Include the timepoint of the definition to the result.
InclRedef	Include the timepoint of the overwrite into the result.

Returns

{ Scatter[] -> DomainWrite[] }

Definition at line 215 of file ZoneAlgo.cpp.

References computeScalarReachingDefinition(), isl::set::get_space(), polly::getScatterSpace(), isl::space::map_from_domain_and_range(), and polly::singleton().

computeScalarReachingDefinition() [2/2]

static isl::union_map computeScalarReachingDefinition ( isl::union_map  Schedule, isl::union_set  Writes, bool  InclDef, bool  InclRedef  )

static

Compute the reaching definition of a scalar.

Compared to computeReachingDefinition, there is just one element which is accessed and therefore only a set if instances that accesses that element is required.

Parameters

Schedule	{ DomainWrite[] -> Scatter[] }
Writes	{ DomainWrite[] }
InclDef	Include the timepoint of the definition to the result.
InclRedef	Include the timepoint of the overwrite into the result.

Returns

{ Scatter[] -> DomainWrite[] }

Definition at line 189 of file ZoneAlgo.cpp.

References computeReachingDefinition(), and isl::union_map::from_domain().

Referenced by computeScalarReachingDefinition(), and polly::ZoneAlgorithm::getScalarReachingDefinition().

isInsideLoop()

static bool isInsideLoop ( Loop *  OuterLoop, Loop *  InnerLoop  )

static

Is InnerLoop nested inside OuterLoop?

Definition at line 317 of file ZoneAlgo.cpp.

Referenced by polly::ZoneAlgorithm::getDefToTarget().

isMapToUnknown()

static bool isMapToUnknown ( const isl::map &  Map )

static

Return whether Map maps to an unknown value.

Parameters

{	[] -> ValInst[] }

Definition at line 247 of file ZoneAlgo.cpp.

References isl::space::dim(), isl::map::get_space(), isl::space::has_tuple_id(), isl::boolean::is_false(), isl::space::is_wrapping(), isl::space::range(), isl::size::release(), and isl::set.

Referenced by polly::filterKnownValInst().

isRecursivePHI()

static bool isRecursivePHI ( const PHINode *  PHI )

static

Return whether PHI refers (also transitively through other PHIs) to itself.

loop: phi1 = phi [0, preheader], [phi1, loop] br i1 c, label loop, label exit

exit: phi2 = phi [phi1, bb]

In this example, phi1 is recursive, but phi2 is not.

Definition at line 511 of file ZoneAlgo.cpp.

References polly::PHI, and polly::Value.

Referenced by polly::ZoneAlgorithm::computeNormalizedPHIs().

makeUnknownForDomain()

static isl::map makeUnknownForDomain ( isl::set  Domain )

static

Create a domain-to-unknown value mapping.

See also

makeUnknownForDomain(isl::union_set)

Parameters

Domain

{ Domain[] }

Returns

{ Domain[] -> ValInst[] }

Definition at line 240 of file ZoneAlgo.cpp.

References Domain, and isl::map::from_domain().

normalizeValInst()

static isl::union_map normalizeValInst ( isl::union_map  Input, const DenseSet< PHINode * > &  ComputedPHIs, isl::union_map  NormalizeMap  )

static

Remove all computed PHIs out of Input and replace by their incoming value.

Parameters

Input	{ [] -> ValInst[] }
ComputedPHIs	Set of PHIs that are replaced. Its ValInst must appear on the LHS of NormalizeMap.
NormalizeMap	{ ValInst[] -> ValInst[] }

Definition at line 848 of file ZoneAlgo.cpp.

References isl::union_map::apply_range(), isl::union_map::ctx(), isl::union_map::empty(), isl::union_map::get_map_list(), isl::space::get_tuple_id(), isl::id::get_user(), isl::space::is_wrapping(), isl::out, polly::PHI, isl::space::range(), isl::union_map::unite(), isl::space::unwrap(), and polly::Value.

Referenced by polly::ZoneAlgorithm::computeNormalizedPHIs(), and polly::ZoneAlgorithm::makeNormalizedValInst().

onlySameValueWrites()

static bool onlySameValueWrites ( ScopStmt *  Stmt )

static

Check if all stores in Stmt store the very same value.

This covers a special situation occurring in Polybench's covariance/correlation (which is typical for algorithms that cover symmetric matrices):

for (int i = 0; i < n; i += 1) for (int j = 0; j <= i; j += 1) { double x = ...; C[i][j] = x; C[j][i] = x; }

For i == j, the same value is written twice to the same element.Double writes to the same element are not allowed in DeLICM because its algorithm does not see which of the writes is effective.But if its the same value anyway, it doesn't matter.

LLVM passes, however, cannot simplify this because the write is necessary for i != j (unless it would add a condition for one of the writes to occur only if i != j).

TODO: In the future we may want to extent this to make the checks specific to different memory locations.

Definition at line 297 of file ZoneAlgo.cpp.

References polly::Value.

Referenced by polly::ZoneAlgorithm::collectIncompatibleElts().

STATISTIC() [1/5]

STATISTIC	(	NumCompatibleArrays	,
		"Number of zone-analyzable arrays"
	)

STATISTIC() [2/5]

STATISTIC	(	NumIncompatibleArrays	,
		"Number of not zone-analyzable arrays"
	)

STATISTIC() [3/5]

STATISTIC	(	NumNormalizablePHIs	,
		"Number of normalizable PHIs"
	)

STATISTIC() [4/5]

STATISTIC	(	NumPHINormialization	,
		"Number of PHI executed normalizations"
	)

STATISTIC() [5/5]

STATISTIC	(	NumRecursivePHIs	,
		"Number of recursive PHIs"
	)