Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/Analysis/DivergenceAnalysis.h - Divergence 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

//

//===----------------------------------------------------------------------===//

//

// \file

// The divergence analysis determines which instructions and branches are

// divergent given a set of divergent source instructions.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DIVERGENCEANALYSIS_H

#define LLVM_ANALYSIS_DIVERGENCEANALYSIS_H

#include "llvm/ADT/DenseSet.h"

#include "llvm/Analysis/SyncDependenceAnalysis.h"

#include "llvm/IR/PassManager.h"

#include <vector>

namespace llvm {

class Function;

class Instruction;

class Loop;

class raw_ostream;

class TargetTransformInfo;

class Value;

/// \brief Generic divergence analysis for reducible CFGs.

///

/// This analysis propagates divergence in a data-parallel context from sources

/// of divergence to all users. It requires reducible CFGs. All assignments

/// should be in SSA form.

class DivergenceAnalysisImpl {

public:

  /// \brief This instance will analyze the whole function \p F or the loop \p

  /// RegionLoop.

  ///

  /// \param RegionLoop if non-null the analysis is restricted to \p RegionLoop.

  /// Otherwise the whole function is analyzed.

  /// \param IsLCSSAForm whether the analysis may assume that the IR in the

  /// region in LCSSA form.

  DivergenceAnalysisImpl(const Function &F, const Loop *RegionLoop,

                         const DominatorTree &DT, const LoopInfo &LI,

                         SyncDependenceAnalysis &SDA, bool IsLCSSAForm);

  /// \brief The loop that defines the analyzed region (if any).

  const Loop *getRegionLoop() const { return RegionLoop; }

  const Function &getFunction() const { return F; }

  /// \brief Whether \p BB is part of the region.

  bool inRegion(const BasicBlock &BB) const;

  /// \brief Whether \p I is part of the region.

  bool inRegion(const Instruction &I) const;

  /// \brief Mark \p UniVal as a value that is always uniform.

  void addUniformOverride(const Value &UniVal);

  /// \brief Mark \p DivVal as a value that is always divergent. Will not do so

  /// if `isAlwaysUniform(DivVal)`.

  /// \returns Whether the tracked divergence state of \p DivVal changed.

  bool markDivergent(const Value &DivVal);

  /// \brief Propagate divergence to all instructions in the region.

  /// Divergence is seeded by calls to \p markDivergent.

  void compute();

  /// \brief Whether any value was marked or analyzed to be divergent.

  bool hasDetectedDivergence() const { return !DivergentValues.empty(); }

  /// \brief Whether \p Val will always return a uniform value regardless of its

  /// operands

  bool isAlwaysUniform(const Value &Val) const;

  /// \brief Whether \p Val is divergent at its definition.

  bool isDivergent(const Value &Val) const;

  /// \brief Whether \p U is divergent. Uses of a uniform value can be

  /// divergent.

  bool isDivergentUse(const Use &U) const;

private:

  /// \brief Mark \p Term as divergent and push all Instructions that become

  /// divergent as a result on the worklist.

  void analyzeControlDivergence(const Instruction &Term);

  /// \brief Mark all phi nodes in \p JoinBlock as divergent and push them on

  /// the worklist.

  void taintAndPushPhiNodes(const BasicBlock &JoinBlock);

  /// \brief Identify all Instructions that become divergent because \p DivExit

  /// is a divergent loop exit of \p DivLoop. Mark those instructions as

  /// divergent and push them on the worklist.

  void propagateLoopExitDivergence(const BasicBlock &DivExit,

                                   const Loop &DivLoop);

  /// \brief Internal implementation function for propagateLoopExitDivergence.

  void analyzeLoopExitDivergence(const BasicBlock &DivExit,

                                 const Loop &OuterDivLoop);

  /// \brief Mark all instruction as divergent that use a value defined in \p

  /// OuterDivLoop. Push their users on the worklist.

  void analyzeTemporalDivergence(const Instruction &I,

                                 const Loop &OuterDivLoop);

  /// \brief Push all users of \p Val (in the region) to the worklist.

  void pushUsers(const Value &I);

  /// \brief Whether \p Val is divergent when read in \p ObservingBlock.

  bool isTemporalDivergent(const BasicBlock &ObservingBlock,

                           const Value &Val) const;

private:

  const Function &F;

  // If regionLoop != nullptr, analysis is only performed within \p RegionLoop.

  // Otherwise, analyze the whole function

  const Loop *RegionLoop;

  const DominatorTree &DT;

  const LoopInfo &LI;

  // Recognized divergent loops

  DenseSet<const Loop *> DivergentLoops;

  // The SDA links divergent branches to divergent control-flow joins.

  SyncDependenceAnalysis &SDA;

  // Use simplified code path for LCSSA form.

  bool IsLCSSAForm;

  // Set of known-uniform values.

  DenseSet<const Value *> UniformOverrides;

  // Detected/marked divergent values.

  DenseSet<const Value *> DivergentValues;

  // Internal worklist for divergence propagation.

  std::vector<const Instruction *> Worklist;

};

class DivergenceInfo {

  Function &F;

  // If the function contains an irreducible region the divergence

  // analysis can run indefinitely. We set ContainsIrreducible and no

  // analysis is actually performed on the function. All values in

  // this function are conservatively reported as divergent instead.

  bool ContainsIrreducible = false;

  std::unique_ptr<SyncDependenceAnalysis> SDA;

  std::unique_ptr<DivergenceAnalysisImpl> DA;

public:

  DivergenceInfo(Function &F, const DominatorTree &DT,

                 const PostDominatorTree &PDT, const LoopInfo &LI,

                 const TargetTransformInfo &TTI, bool KnownReducible);

  /// Whether any divergence was detected.

  bool hasDivergence() const {

    return ContainsIrreducible || DA->hasDetectedDivergence();

  }

  /// The GPU kernel this analysis result is for

  const Function &getFunction() const { return F; }

  /// Whether \p V is divergent at its definition.

  bool isDivergent(const Value &V) const {

    return ContainsIrreducible || DA->isDivergent(V);

  }

  /// Whether \p U is divergent. Uses of a uniform value can be divergent.

  bool isDivergentUse(const Use &U) const {

    return ContainsIrreducible || DA->isDivergentUse(U);

  }

  /// Whether \p V is uniform/non-divergent.

  bool isUniform(const Value &V) const { return !isDivergent(V); }

  /// Whether \p U is uniform/non-divergent. Uses of a uniform value can be

  /// divergent.

  bool isUniformUse(const Use &U) const { return !isDivergentUse(U); }

};

/// \brief Divergence analysis frontend for GPU kernels.

class DivergenceAnalysis : public AnalysisInfoMixin<DivergenceAnalysis> {

  friend AnalysisInfoMixin<DivergenceAnalysis>;

  static AnalysisKey Key;

public:

  using Result = DivergenceInfo;

  /// Runs the divergence analysis on @F, a GPU kernel

  Result run(Function &F, FunctionAnalysisManager &AM);

};

/// Printer pass to dump divergence analysis results.

struct DivergenceAnalysisPrinterPass

    : public PassInfoMixin<DivergenceAnalysisPrinterPass> {

  DivergenceAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);

private:

  raw_ostream &OS;

}; // class DivergenceAnalysisPrinterPass

} // namespace llvm

#endif // LLVM_ANALYSIS_DIVERGENCEANALYSIS_H