EIC code displayed by LXR master/​include/​polly/​ZoneAlgo.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:48:21

 //===------ 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 */

This page was automatically generated by the 2.3.7 LXR engine. The LXR team