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

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

 //===--- polly/DependenceInfo.h - Polyhedral dependency analysis *- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Calculate the data dependency relations for a Scop using ISL.
 //
 // The integer set library (ISL) from Sven has an integrated dependency analysis
 // to calculate data dependences. This pass takes advantage of this and
 // calculates those dependences of a Scop.
 //
 // The dependences in this pass are exact in terms that for a specific read
 // statement instance only the last write statement instance is returned. In
 // case of may-writes, a set of possible write instances is returned. This
 // analysis will never produce redundant dependences.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_DEPENDENCE_INFO_H
 #define POLLY_DEPENDENCE_INFO_H
 
 #include "polly/ScopPass.h"
 #include "isl/ctx.h"
 #include "isl/isl-noexceptions.h"
 
 namespace polly {
 
 /// The accumulated dependence information for a SCoP.
 ///
 /// The Dependences struct holds all dependence information we collect and
 /// compute for one SCoP. It also offers an interface that allows users to
 /// query only specific parts.
 class Dependences final {
 public:
   // Granularities of the current dependence analysis
   enum AnalysisLevel {
     AL_Statement = 0,
     // Distinguish accessed memory references in the same statement
     AL_Reference,
     // Distinguish memory access instances in the same statement
     AL_Access,
 
     NumAnalysisLevels
   };
 
   /// Map type for reduction dependences.
   using ReductionDependencesMapTy = DenseMap<MemoryAccess *, isl_map *>;
 
   /// Map type to associate statements with schedules.
   using StatementToIslMapTy = DenseMap<ScopStmt *, isl::map>;
 
   /// The type of the dependences.
   ///
   /// Reduction dependences are separated from RAW/WAW/WAR dependences because
   /// we can ignore them during the scheduling. That's because the order
   /// in which the reduction statements are executed does not matter. However,
   /// if they are executed in parallel we need to take additional measures
   /// (e.g, privatization) to ensure a correct result. The (reverse) transitive
   /// closure of the reduction dependences are used to check for parallel
   /// executed reduction statements during code generation. These dependences
   /// connect all instances of a reduction with each other, they are therefore
   /// cyclic and possibly "reversed".
   enum Type {
     // Write after read
     TYPE_WAR = 1 << 0,
 
     // Read after write
     TYPE_RAW = 1 << 1,
 
     // Write after write
     TYPE_WAW = 1 << 2,
 
     // Reduction dependences
     TYPE_RED = 1 << 3,
 
     // Transitive closure of the reduction dependences (& the reverse)
     TYPE_TC_RED = 1 << 4,
   };
 
   const std::shared_ptr<isl_ctx> &getSharedIslCtx() const { return IslCtx; }
 
   /// Get the dependences of type @p Kinds.
   ///
   /// @param Kinds This integer defines the different kinds of dependences
   ///              that will be returned. To return more than one kind, the
   ///              different kinds are 'ored' together.
   isl::union_map getDependences(int Kinds) const;
 
   /// Report if valid dependences are available.
   bool hasValidDependences() const;
 
   /// Return the reduction dependences caused by @p MA.
   ///
   /// @return The reduction dependences caused by @p MA or nullptr if none.
   __isl_give isl_map *getReductionDependences(MemoryAccess *MA) const;
 
   /// Return all reduction dependences.
   const ReductionDependencesMapTy &getReductionDependences() const {
     return ReductionDependences;
   }
 
   /// Check if a partial schedule is parallel wrt to @p Deps.
   ///
   /// @param Schedule       The subset of the schedule space that we want to
   ///                       check.
   /// @param Deps           The dependences @p Schedule needs to respect.
   /// @param MinDistancePtr If not nullptr, the minimal dependence distance will
   ///                       be returned at the address of that pointer
   ///
   /// @return Returns true, if executing parallel the outermost dimension of
   ///         @p Schedule is valid according to the dependences @p Deps.
   bool isParallel(__isl_keep isl_union_map *Schedule,
                   __isl_take isl_union_map *Deps,
                   __isl_give isl_pw_aff **MinDistancePtr = nullptr) const;
 
   /// Check if a new schedule is valid.
   ///
   /// @param S             The current SCoP.
   /// @param NewSchedules  The new schedules
   ///
   /// @return True if the new schedule is valid, false if it reverses
   ///         dependences.
   bool isValidSchedule(Scop &S, const StatementToIslMapTy &NewSchedules) const;
 
   /// Return true of the schedule @p NewSched is a schedule for @S that does not
   /// violate any dependences.
   bool isValidSchedule(Scop &S, isl::schedule NewSched) const;
 
   /// Print the stored dependence information.
   void print(llvm::raw_ostream &OS) const;
 
   /// Dump the dependence information stored to the dbgs stream.
   void dump() const;
 
   /// Return the granularity of this dependence analysis.
   AnalysisLevel getDependenceLevel() { return Level; }
 
   /// Allow the DependenceInfo access to private members and methods.
   ///
   /// To restrict access to the internal state, only the DependenceInfo class
   /// is able to call or modify a Dependences struct.
   friend struct DependenceAnalysis;
   friend struct DependenceInfoPrinterPass;
   friend class DependenceInfo;
   friend class DependenceInfoWrapperPass;
 
   /// Destructor that will free internal objects.
   ~Dependences() { releaseMemory(); }
 
 private:
   /// Create an empty dependences struct.
   explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx,
                        AnalysisLevel Level)
       : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr),
         IslCtx(IslCtx), Level(Level) {}
 
   /// Calculate and add at the privatization dependences.
   void addPrivatizationDependences();
 
   /// Calculate the dependences for a certain SCoP @p S.
   void calculateDependences(Scop &S);
 
   /// Set the reduction dependences for @p MA to @p Deps.
   void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
 
   /// Free the objects associated with this Dependences struct.
   ///
   /// The Dependences struct will again be "empty" afterwards.
   void releaseMemory();
 
   /// The different basic kinds of dependences we calculate.
   isl_union_map *RAW;
   isl_union_map *WAR;
   isl_union_map *WAW;
 
   /// The special reduction dependences.
   isl_union_map *RED;
 
   /// The (reverse) transitive closure of reduction dependences.
   isl_union_map *TC_RED;
 
   /// Mapping from memory accesses to their reduction dependences.
   ReductionDependencesMapTy ReductionDependences;
 
   /// Isl context from the SCoP.
   std::shared_ptr<isl_ctx> IslCtx;
 
   /// Granularity of this dependence analysis.
   const AnalysisLevel Level;
 };
 
 struct DependenceAnalysis final : public AnalysisInfoMixin<DependenceAnalysis> {
   static AnalysisKey Key;
   struct Result {
     Scop &S;
     std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
 
     /// Return the dependence information for the current SCoP.
     ///
     /// @param Level The granularity of dependence analysis result.
     ///
     /// @return The dependence analysis result
     ///
     const Dependences &getDependences(Dependences::AnalysisLevel Level);
 
     /// Recompute dependences from schedule and memory accesses.
     const Dependences &recomputeDependences(Dependences::AnalysisLevel Level);
 
     /// Invalidate the dependence information and recompute it when needed
     /// again.
     /// May be required when the underlying Scop was changed in a way that
     /// would add new dependencies (e.g. between new statement instances
     /// insierted into the SCoP) or intentionally breaks existing ones. It is
     /// not required when updating the schedule that conforms the existing
     /// dependencies.
     void abandonDependences();
   };
   Result run(Scop &S, ScopAnalysisManager &SAM,
              ScopStandardAnalysisResults &SAR);
 };
 
 struct DependenceInfoPrinterPass final
     : PassInfoMixin<DependenceInfoPrinterPass> {
   DependenceInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
 
   PreservedAnalyses run(Scop &S, ScopAnalysisManager &,
                         ScopStandardAnalysisResults &, SPMUpdater &);
 
   raw_ostream &OS;
 };
 
 class DependenceInfo final : public ScopPass {
 public:
   static char ID;
 
   /// Construct a new DependenceInfo pass.
   DependenceInfo() : ScopPass(ID) {}
 
   /// Return the dependence information for the current SCoP.
   ///
   /// @param Level The granularity of dependence analysis result.
   ///
   /// @return The dependence analysis result
   ///
   const Dependences &getDependences(Dependences::AnalysisLevel Level);
 
   /// Recompute dependences from schedule and memory accesses.
   const Dependences &recomputeDependences(Dependences::AnalysisLevel Level);
 
   /// Invalidate the dependence information and recompute it when needed again.
   /// May be required when the underlying Scop was changed in a way that would
   /// add new dependencies (e.g. between new statement instances insierted into
   /// the SCoP) or intentionally breaks existing ones. It is not required when
   /// updating the schedule that conforms the existing dependencies.
   void abandonDependences();
 
   /// Compute the dependence information for the SCoP @p S.
   bool runOnScop(Scop &S) override;
 
   /// Print the dependences for the given SCoP to @p OS.
   void printScop(raw_ostream &OS, Scop &) const override;
 
   /// Release the internal memory.
   void releaseMemory() override {
     for (auto &d : D)
       d.reset();
   }
 
   /// Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
   Scop *S;
 
   /// Dependences struct for the current SCoP.
   std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
 };
 
 llvm::Pass *createDependenceInfoPass();
 llvm::Pass *createDependenceInfoPrinterLegacyPass(llvm::raw_ostream &OS);
 
 /// Construct a new DependenceInfoWrapper pass.
 class DependenceInfoWrapperPass final : public FunctionPass {
 public:
   static char ID;
 
   /// Construct a new DependenceInfoWrapper pass.
   DependenceInfoWrapperPass() : FunctionPass(ID) {}
 
   /// Return the dependence information for the given SCoP.
   ///
   /// @param S     SCoP object.
   /// @param Level The granularity of dependence analysis result.
   ///
   /// @return The dependence analysis result
   ///
   const Dependences &getDependences(Scop *S, Dependences::AnalysisLevel Level);
 
   /// Recompute dependences from schedule and memory accesses.
   const Dependences &recomputeDependences(Scop *S,
                                           Dependences::AnalysisLevel Level);
 
   /// Compute the dependence information on-the-fly for the function.
   bool runOnFunction(Function &F) override;
 
   /// Print the dependences for the current function to @p OS.
   void print(raw_ostream &OS, const Module *M = nullptr) const override;
 
   /// Release the internal memory.
   void releaseMemory() override { ScopToDepsMap.clear(); }
 
   /// Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
   using ScopToDepsMapTy = DenseMap<Scop *, std::unique_ptr<Dependences>>;
 
   /// Scop to Dependence map for the current function.
   ScopToDepsMapTy ScopToDepsMap;
 };
 
 llvm::Pass *createDependenceInfoWrapperPassPass();
 llvm::Pass *
 createDependenceInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS);
 
 } // namespace polly
 
 namespace llvm {
 void initializeDependenceInfoPass(llvm::PassRegistry &);
 void initializeDependenceInfoPrinterLegacyPassPass(llvm::PassRegistry &);
 void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &);
 void initializeDependenceInfoPrinterLegacyFunctionPassPass(
     llvm::PassRegistry &);
 } // namespace llvm
 
 #endif

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