//===------ ZoneAlgo.h ------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Derive information about array elements between statements ("Zones").
//
//===----------------------------------------------------------------------===//
#ifndef POLLY_ZONEALGO_H
#define POLLY_ZONEALGO_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "isl/isl-noexceptions.h"
#include <memory>
namespace llvm {
class Value;
class LoopInfo;
class Loop;
class PHINode;
class raw_ostream;
} // namespace llvm
namespace polly {
class Scop;
class ScopStmt;
class MemoryAccess;
class ScopArrayInfo;
/// Return only the mappings that map to known values.
///
/// @param UMap { [] -> ValInst[] }
///
/// @return { [] -> ValInst[] }
isl::union_map filterKnownValInst(const isl::union_map &UMap);
/// Base class for algorithms based on zones, like DeLICM.
class ZoneAlgorithm {
protected:
/// The name of the pass this is used from. Used for optimization remarks.
const char *PassName;
/// Hold a reference to the isl_ctx to avoid it being freed before we released
/// all of the isl objects.
///
/// This must be declared before any other member that holds an isl object.
/// This guarantees that the shared_ptr and its isl_ctx is destructed last,
/// after all other members free'd the isl objects they were holding.
std::shared_ptr<isl_ctx> IslCtx;
/// Cached reaching definitions for each ScopStmt.
///
/// Use getScalarReachingDefinition() to get its contents.
llvm::DenseMap<ScopStmt *, isl::map> ScalarReachDefZone;
/// The analyzed Scop.
Scop *S;
/// LoopInfo analysis used to determine whether values are synthesizable.
llvm::LoopInfo *LI;
/// Parameter space that does not need realignment.
isl::space ParamSpace;
/// Space the schedule maps to.
isl::space ScatterSpace;
/// Cached version of the schedule and domains.
isl::union_map Schedule;
/// Combined access relations of all MemoryKind::Array READ accesses.
/// { DomainRead[] -> Element[] }
isl::union_map AllReads;
/// The loaded values (llvm::LoadInst) of all reads.
/// { [Element[] -> DomainRead[]] -> ValInst[] }
isl::union_map AllReadValInst;
/// Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.
/// { DomainMayWrite[] -> Element[] }
isl::union_map AllMayWrites;
/// Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.
/// { DomainMustWrite[] -> Element[] }
isl::union_map AllMustWrites;
/// Combined access relations of all MK_Array write accesses (union of
/// AllMayWrites and AllMustWrites).
/// { DomainWrite[] -> Element[] }
isl::union_map AllWrites;
/// The value instances written to array elements of all write accesses.
/// { [Element[] -> DomainWrite[]] -> ValInst[] }
isl::union_map AllWriteValInst;
/// All reaching definitions for MemoryKind::Array writes.
/// { [Element[] -> Zone[]] -> DomainWrite[] }
isl::union_map WriteReachDefZone;
/// Map llvm::Values to an isl identifier.
/// Used with -polly-use-llvm-names=false as an alternative method to get
/// unique ids that do not depend on pointer values.
llvm::DenseMap<llvm::Value *, isl::id> ValueIds;
/// Set of array elements that can be reliably used for zone analysis.
/// { Element[] }
isl::union_set CompatibleElts;
/// List of PHIs that may transitively refer to themselves.
///
/// Computing them would require a polyhedral transitive closure operation,
/// for which isl may only return an approximation. For correctness, we always
/// require an exact result. Hence, we exclude such PHIs.
llvm::SmallPtrSet<llvm::PHINode *, 4> RecursivePHIs;
/// PHIs that have been computed.
///
/// Computed PHIs are replaced by their incoming values using #NormalizeMap.
llvm::DenseSet<llvm::PHINode *> ComputedPHIs;
/// For computed PHIs, contains the ValInst they stand for.
///
/// To show an example, assume the following PHINode:
///
/// Stmt:
/// %phi = phi double [%val1, %bb1], [%val2, %bb2]
///
/// It's ValInst is:
///
/// { [Stmt[i] -> phi[]] }
///
/// The value %phi will be either %val1 or %val2, depending on whether in
/// iteration i %bb1 or %bb2 has been executed before. In SCoPs, this can be
/// determined at compile-time, and the result stored in #NormalizeMap. For
/// the previous example, it could be:
///
/// { [Stmt[i] -> phi[]] -> [Stmt[0] -> val1[]];
/// [Stmt[i] -> phi[]] -> [Stmt[i] -> val2[]] : i > 0 }
///
/// Only ValInsts in #ComputedPHIs are present in this map. Other values are
/// assumed to represent themselves. This is to avoid adding lots of identity
/// entries to this map.
///
/// { PHIValInst[] -> IncomingValInst[] }
isl::union_map NormalizeMap;
/// Cache for computePerPHI(const ScopArrayInfo *)
llvm::SmallDenseMap<llvm::PHINode *, isl::union_map> PerPHIMaps;
/// A cache for getDefToTarget().
llvm::DenseMap<std::pair<ScopStmt *, ScopStmt *>, isl::map> DefToTargetCache;
/// Prepare the object before computing the zones of @p S.
///
/// @param PassName Name of the pass using this analysis.
/// @param S The SCoP to process.
/// @param LI LoopInfo analysis used to determine synthesizable values.
ZoneAlgorithm(const char *PassName, Scop *S, llvm::LoopInfo *LI);
private:
/// Find the array elements that violate the zone analysis assumptions.
///
/// What violates our assumptions:
/// - A load after a write of the same location; we assume that all reads
/// occur before the writes.
/// - Two writes to the same location; we cannot model the order in which
/// these occur.
///
/// Scalar reads implicitly always occur before other accesses therefore never
/// violate the first condition. There is also at most one write to a scalar,
/// satisfying the second condition.
///
/// @param Stmt The statement to be analyzed.
/// @param[out] IncompatibleElts Receives the elements that are not
/// zone-analysis compatible.
/// @param[out] AllElts receives all encountered elements.
void collectIncompatibleElts(ScopStmt *Stmt, isl::union_set &IncompatibleElts,
isl::union_set &AllElts);
void addArrayReadAccess(MemoryAccess *MA);
/// Return the ValInst write by a (must-)write access. Returns the 'unknown'
/// ValInst if there is no single ValInst[] the array element written to will
/// have.
///
/// @return { ValInst[] }
isl::union_map getWrittenValue(MemoryAccess *MA, isl::map AccRel);
void addArrayWriteAccess(MemoryAccess *MA);
/// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a
/// use in every instance of @p UseStmt.
///
/// @param UseStmt Statement a scalar is used in.
/// @param DefStmt Statement a scalar is defined in.
///
/// @return { DomainUse[] -> DomainDef[] }
isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *DefStmt);
protected:
isl::union_set makeEmptyUnionSet() const;
isl::union_map makeEmptyUnionMap() const;
/// For each 'execution' of a PHINode, get the incoming block that was
/// executed before.
///
/// For each PHI instance we can directly determine which was the incoming
/// block, and hence derive which value the PHI has.
///
/// @param SAI The ScopArrayInfo representing the PHI's storage.
///
/// @return { DomainPHIRead[] -> DomainPHIWrite[] }
isl::union_map computePerPHI(const polly::ScopArrayInfo *SAI);
/// Find the array elements that can be used for zone analysis.
void collectCompatibleElts();
/// Get the schedule for @p Stmt.
///
/// The domain of the result is as narrow as possible.
isl::map getScatterFor(ScopStmt *Stmt) const;
/// Get the schedule of @p MA's parent statement.
isl::map getScatterFor(MemoryAccess *MA) const;
/// Get the schedule for the statement instances of @p Domain.
isl::union_map getScatterFor(isl::union_set Domain) const;
/// Get the schedule for the statement instances of @p Domain.
isl::map getScatterFor(isl::set Domain) const;
/// Get the domain of @p Stmt.
isl::set getDomainFor(ScopStmt *Stmt) const;
/// Get the domain @p MA's parent statement.
isl::set getDomainFor(MemoryAccess *MA) const;
/// Get the access relation of @p MA.
///
/// The domain of the result is as narrow as possible.
isl::map getAccessRelationFor(MemoryAccess *MA) const;
/// Get a domain translation map from a (scalar) definition to the statement
/// where the definition is being moved to.
///
/// @p TargetStmt can also be seen at an llvm::Use of an llvm::Value in
/// @p DefStmt. In addition, we allow transitive uses:
///
/// DefStmt -> MiddleStmt -> TargetStmt
///
/// where an operand tree of instructions in DefStmt and MiddleStmt are to be
/// moved to TargetStmt. To be generally correct, we also need to know all the
/// intermediate statements. However, we make use of the fact that
/// ForwardOpTree currently does not support a move from a loop body across
/// its header such that only the first definition and the target statement
/// are relevant.
///
/// @param DefStmt Statement from where a definition might be moved from.
/// @param TargetStmt Statement where the definition is potentially being
/// moved to (should contain a use of that definition).
///
/// @return { DomainDef[] -> DomainTarget[] }
isl::map getDefToTarget(ScopStmt *DefStmt, ScopStmt *TargetStmt);
/// Get the reaching definition of a scalar defined in @p Stmt.
///
/// Note that this does not depend on the llvm::Instruction, only on the
/// statement it is defined in. Therefore the same computation can be reused.
///
/// @param Stmt The statement in which a scalar is defined.
///
/// @return { Scatter[] -> DomainDef[] }
isl::map getScalarReachingDefinition(ScopStmt *Stmt);
/// Get the reaching definition of a scalar defined in @p DefDomain.
///
/// @param DomainDef { DomainDef[] }
/// The write statements to get the reaching definition for.
///
/// @return { Scatter[] -> DomainDef[] }
isl::map getScalarReachingDefinition(isl::set DomainDef);
/// Create a statement-to-unknown value mapping.
///
/// @param Stmt The statement whose instances are mapped to unknown.
///
/// @return { Domain[] -> ValInst[] }
isl::map makeUnknownForDomain(ScopStmt *Stmt) const;
/// Create an isl_id that represents @p V.
isl::id makeValueId(llvm::Value *V);
/// Create the space for an llvm::Value that is available everywhere.
isl::space makeValueSpace(llvm::Value *V);
/// Create a set with the llvm::Value @p V which is available everywhere.
isl::set makeValueSet(llvm::Value *V);
/// Create a mapping from a statement instance to the instance of an
/// llvm::Value that can be used in there.
///
/// Although LLVM IR uses single static assignment, llvm::Values can have
/// different contents in loops, when they get redefined in the last
/// iteration. This function tries to get the statement instance of the
/// previous definition, relative to a user.
///
/// Example:
/// for (int i = 0; i < N; i += 1) {
/// DEF:
/// int v = A[i];
/// USE:
/// use(v);
/// }
///
/// The value instance used by statement instance USE[i] is DEF[i]. Hence,
/// makeValInst returns:
///
/// { USE[i] -> [DEF[i] -> v[]] : 0 <= i < N }
///
/// @param Val The value to get the instance of.
/// @param UserStmt The statement that uses @p Val. Can be nullptr.
/// @param Scope Loop the using instruction resides in.
/// @param IsCertain Pass true if the definition of @p Val is a
/// MUST_WRITE or false if the write is conditional.
///
/// @return { DomainUse[] -> ValInst[] }
isl::map makeValInst(llvm::Value *Val, ScopStmt *UserStmt, llvm::Loop *Scope,
bool IsCertain = true);
/// Create and normalize a ValInst.
///
/// @see makeValInst
/// @see normalizeValInst
/// @see #NormalizedPHI
isl::union_map makeNormalizedValInst(llvm::Value *Val, ScopStmt *UserStmt,
llvm::Loop *Scope,
bool IsCertain = true);
/// Return whether @p MA can be used for transformations (e.g. OpTree load
/// forwarding, DeLICM mapping).
bool isCompatibleAccess(MemoryAccess *MA);
/// Compute the different zones.
void computeCommon();
/// Compute the normalization map that replaces PHIs by their incoming
/// values.
///
/// @see #NormalizeMap
void computeNormalizedPHIs();
/// Print the current state of all MemoryAccesses to @p.
void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const;
/// Is @p MA a PHI READ access that can be normalized?
///
/// @see #NormalizeMap
bool isNormalizable(MemoryAccess *MA);
/// @{
/// Determine whether the argument does not map to any computed PHI. Those
/// should have been replaced by their incoming values.
///
/// @see #NormalizedPHI
isl::boolean isNormalized(isl::map Map);
isl::boolean isNormalized(isl::union_map Map);
/// @}
public:
/// Return the SCoP this object is analyzing.
Scop *getScop() const { return S; }
/// A reaching definition zone is known to have the definition's written value
/// if the definition is a MUST_WRITE.
///
/// @return { [Element[] -> Zone[]] -> ValInst[] }
isl::union_map computeKnownFromMustWrites() const;
/// A reaching definition zone is known to be the same value as any load that
/// reads from that array element in that period.
///
/// @return { [Element[] -> Zone[]] -> ValInst[] }
isl::union_map computeKnownFromLoad() const;
/// Compute which value an array element stores at every instant.
///
/// @param FromWrite Use stores as source of information.
/// @param FromRead Use loads as source of information.
///
/// @return { [Element[] -> Zone[]] -> ValInst[] }
isl::union_map computeKnown(bool FromWrite, bool FromRead) const;
};
/// Create a domain-to-unknown value mapping.
///
/// Value instances that do not represent a specific value are represented by an
/// unnamed tuple of 0 dimensions. Its meaning depends on the context. It can
/// either mean a specific but unknown value which cannot be represented by
/// other means. It conflicts with itself because those two unknown ValInsts may
/// have different concrete values at runtime.
///
/// The other meaning is an arbitrary or wildcard value that can be chosen
/// freely, like LLVM's undef. If matched with an unknown ValInst, there is no
/// conflict.
///
/// @param Domain { Domain[] }
///
/// @return { Domain[] -> ValInst[] }
isl::union_map makeUnknownForDomain(isl::union_set Domain);
} // namespace polly
#endif /* POLLY_ZONEALGO_H */